Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, 2009, том 16, выпуск 2, страницы 16–20 (Mi da565)  

Эта публикация цитируется в 18 научных статьях (всего в 18 статьях)

Почти правильные 2-раскраски вершин разреженных графов

О. В. Бородинa, А. О. Ивановаb

a Институт математики СО РАН, Новосибирск, Россия
b НИИ математики при Якутском государственном университете, Якутск, Россиия
Список литературы:
Аннотация: Граф G называется (2,1)-раскрашиваемым, если множество его вершин можно разбить на два подмножества V1 и V2 так, что в G[V1] любая компонента содержит не более двух вершин, а в G[V2] нет рёбер. Доказано, что любой граф G с максимальной средней степенью mad(G) меньшей 7/3 является (2,1)-раскрашиваемым. Отсюда следует, что каждый плоский граф с обхватом не менее 14 является (2,1)-раскрашиваемым. Построен плоский граф Gnmad(Gn)=(18n2)/(7n1), не являющийся (2,1)-раскрашиваемым. Библиогр. 5.
Ключевые слова: планарный граф, обхват, раскраска, разбиение.
Статья поступила: 09.02.2008
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2010, Volume 4, Issue 1, Pages 21–23
DOI: https://doi.org/10.1134/S1990478910010047
Реферативные базы данных:
УДК: 519.172.2
Образец цитирования: О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20; J. Appl. Industr. Math., 4:1 (2010), 21–23
Цитирование в формате AMSBIB
\RBibitem{BorIva09}
\by О.~В.~Бородин, А.~О.~Иванова
\paper Почти правильные 2-раскраски вершин разреженных графов
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 2
\pages 16--20
\mathnet{http://mi.mathnet.ru/da565}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2574306}
\zmath{https://zbmath.org/?q=an:1249.05110}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 1
\pages 21--23
\crossref{https://doi.org/10.1134/S1990478910010047}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77949893758}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da565
  • https://www.mathnet.ru/rus/da/v16/i2/p16
  • Эта публикация цитируется в следующих 18 статьяx:
    1. Min Chen, André Raspaud, Weifan Wang, Weiqiang Yu, “An (F3,F5)-partition of planar graphs with girth at least 5”, Discrete Mathematics, 346:2 (2023), 113216  crossref
    2. Chen M. Raspaud A. Yu W., “An (F-1, F-4)-Partition of Graphs With Low Genus and Girth At Least 6”, J. Graph Theory, 99:2 (2022), 186–206  crossref  mathscinet  isi  scopus
    3. Hendrey K., Wood D.R., “Defective and Clustered Choosability of Sparse Graphs”, Comb. Probab. Comput., 28:5 (2019), 791–810  crossref  mathscinet  zmath  isi  scopus
    4. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
    5. Choi H., Choi I., Jeong J., Suh G., “(1, K)-Coloring of Graphs With Girth At Least Five on a Surface”, J. Graph Theory, 84:4 (2017), 521–535  crossref  mathscinet  zmath  isi  scopus
    6. А. Н. Глебов, Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 6 на два леса с длиной цепей не больше 4”, Дискретн. анализ и исслед. опер., 21:2 (2014), 33–51  mathnet  mathscinet; A. N. Glebov, D. Zh. Zambalaeva, “A partition of a planar graph with girth 6 into two forests containing no path of length greater than 4”, J. Appl. Industr. Math., 8:3 (2014), 317–328  crossref
    7. Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202  crossref  mathscinet  zmath  isi  elib  scopus
    8. Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80  crossref  mathscinet  zmath  isi  elib  scopus
    9. Dorbec P., Montassier M., Ochem P., “Vertex Partitions of Graphs Into Cographs and Stars”, J. Graph Theory, 75:1 (2014), 75–90  crossref  mathscinet  zmath  isi  elib  scopus
    10. Esperet L., Montassier M., Ochem P., Pinlou A., “A Complexity Dichotomy for the Coloring of Sparse Graphs”, J. Graph Theory, 73:1 (2013), 85–102  crossref  mathscinet  zmath  isi  elib  scopus
    11. Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649  crossref  mathscinet  zmath  isi  elib  scopus
    12. Alexandr Kostochka, Matthew Yancey, Lecture Notes in Computer Science, 7913, Computer Science – Theory and Applications, 2013, 224  crossref
    13. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “(k,1)-coloring of sparse graphs”, Discrete Math., 312:6 (2012), 1128–1135  crossref  mathscinet  zmath  isi  elib  scopus
    14. О. В. Бородин, А. В. Косточка, “Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более 1”, Сиб. матем. журн., 52:5 (2011), 1004–1010  mathnet  mathscinet; O. V. Borodin, A. V. Kostochka, “Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1”, Siberian Math. J., 52:5 (2011), 796–801  crossref  isi
    15. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “(k,j)-coloring of sparse graphs”, Discrete Appl. Math., 159:17 (2011), 1947–1953  crossref  mathscinet  zmath  isi  elib  scopus
    16. Borodin O.V., Ivanova A.O., “List strong linear 2-arboricity of sparse graphs”, J. Graph Theory, 67:2 (2011), 83–90  crossref  mathscinet  zmath  isi  elib  scopus
    17. Borodin O.V., Ivanova A.O., Montassier M., Ochem P., Raspaud A., “Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k”, J. Graph Theory, 65:2 (2010), 83–93  crossref  mathscinet  zmath  isi  elib  scopus
    18. Montassier M., Raspaud A., Zhu Xuding, “Decomposition of sparse graphs into two forests, one having bounded maximum degree”, Inform. Process. Lett., 110:20 (2010), 913–916  crossref  mathscinet  zmath  isi  elib  scopus
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:636
    PDF полного текста:119
    Список литературы:64
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025