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

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

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



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






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


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

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

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

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

a Институт математики СО РАН, Новосибирск, Россия
b НИИ математики при Якутском государственном университете, Якутск, Россиия

Аннотация: Граф $G$ называется $(2,1)$-раскрашиваемым, если множество его вершин можно разбить на два подмножества $V_1$ и $V_2$ так, что в $G[V_1]$ любая компонента содержит не более двух вершин, а в $G[V_2]$ нет рёбер. Доказано, что любой граф $G$ с максимальной средней степенью $\mathrm{mad}(G)$ меньшей 7/3 является $(2,1)$-раскрашиваемым. Отсюда следует, что каждый плоский граф с обхватом не менее 14 является $(2,1)$-раскрашиваемым. Построен плоский граф $G_n$$\mathrm{mad}(G_n)=(18n-2)/(7n-1)$, не являющийся $(2,1)$-раскрашиваемым. Библиогр. 5.

Ключевые слова: планарный граф, обхват, раскраска, разбиение.

Полный текст: PDF файл (671 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2010, 4:1, 21–23

Реферативные базы данных:

УДК: 519.172.2
Статья поступила: 09.02.2008

Образец цитирования: О. В. Бородин, А. О. Иванова, “Почти правильные 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://www.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{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77949893758}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da565
  • http://mi.mathnet.ru/rus/da/v16/i2/p16

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. 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
    2. 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
    3. О. В. Бородин, А. В. Косточка, “Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более $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
    4. 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
    5. 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
    6. 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
    7. 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
    8. 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
    9. А. Н. Глебов, Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 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
    10. 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
    11. 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
    12. 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
    13. 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
    14. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:433
    Полный текст:77
    Литература:34
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019