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

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

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



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






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


Сиб. матем. журн., 2017, том 58, номер 1, страницы 36–47 (Mi smj2837)  

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

О DP-раскраске графов и мультиграфов

А. Ю. Бернштейнa, А. В. Косточкаab, С. П. Проньc

a Университет штата Иллинойс, кафедра математики, Урбана, США
b Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
c Алтайский гос. университет, факультет математики и информационных технологий, пр. Ленина, 61, Барнаул 656002

Аннотация: При решении задачи о предписанной раскраске плоских графов Дворжак и Постл ввели понятие DP-раскраски (они назвали его correspondence coloring). DP-раскраска графа $G$ сводит задачу поиска раскраски $G$ для заданного предписания $L$ к проблеме поиска “большого” независимого множества во вспомогательном графе $H(G,L)$ с множеством вершин $\{(v,c)\colon v\in V(G) и c\in L(v)\}$. Это похоже на сведение В. Г. Визинга и Г. С. Плесневича задачи $k$-раскраски к проблеме поиска независимого множества размера $|V(G)|$ в декартовом произведении $G\square K_k$, но DP-раскраска представляется значительно более полезной, чем сведение В. Г. Визинга и Г. С. Плесневича. Некоторые свойства DP-хроматического числа $\chi_\mathrm{DP}(G)$ напоминают свойства предписанного хроматического числа $\chi_\ell(G)$, но некоторые отличия довольно существенны. Всегда $\chi_\mathrm{DP}(G)\geq\chi_\ell(G)$. Целью настоящей работы является введение DP-раскраски для мультиграфов и доказательство аналога результата O. B. Бородина и Эрдёша–Рубина–Тейлора, характеризующего мультиграфы, которые не допускают DP-раскрасок для некоторых степенных предписаний. Из этого результата следует аналог для DP-раскраски теоремы Галлаи о минимальном числе ребер в критических $k$-хроматических графах.

Ключевые слова: степень вершины, предписанная раскраска, критический граф.

Финансовая поддержка Номер гранта
Illinois Distinguished Fellowship
Российский фонд фундаментальных исследований 15-01-05867
16-01-00499
National Science Foundation DMS-1266016
DMS-1600592
Работа выполнена первым автором при финансовой поддержке стипендии штата Иллинойс, вторым автором – при финансовой поддержке Российского фонда фундаментальных исследований (коды проектов 15-01-05867, 16-01-00499), a также грантов NSF (DMS-1266016, DMS-1600592).


DOI: https://doi.org/10.17377/smzh.2017.58.104

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

Англоязычная версия:
Siberian Mathematical Journal, 2017, 58:1, 28–36

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

Тип публикации: Статья
УДК: 519.17
MSC: 35R30
Статья поступила: 21.03.2016

Образец цитирования: А. Ю. Бернштейн, А. В. Косточка, С. П. Пронь, “О DP-раскраске графов и мультиграфов”, Сиб. матем. журн., 58:1 (2017), 36–47; Siberian Math. J., 58:1 (2017), 28–36

Цитирование в формате AMSBIB
\RBibitem{BerKosPro17}
\by А.~Ю.~Бернштейн, А.~В.~Косточка, С.~П.~Пронь
\paper О~DP-раскраске графов и~мультиграфов
\jour Сиб. матем. журн.
\yr 2017
\vol 58
\issue 1
\pages 36--47
\mathnet{http://mi.mathnet.ru/smj2837}
\crossref{https://doi.org/10.17377/smzh.2017.58.104}
\elib{https://elibrary.ru/item.asp?id=29159900}
\transl
\jour Siberian Math. J.
\yr 2017
\vol 58
\issue 1
\pages 28--36
\crossref{https://doi.org/10.1134/S0037446617010049}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000396065100004}
\elib{https://elibrary.ru/item.asp?id=29493337}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014734354}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/smj2837
  • http://mi.mathnet.ru/rus/smj/v58/i1/p36

    ОТПРАВИТЬ: 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. Bang-Jensen J., Bellitto T., Schweser T., Stiebitz M., “on Dp-Coloring of Digraphs”, J. Graph Theory  crossref  mathscinet  isi  scopus
    2. А. Ю. Бернштейн, А. В. Косточка, “Об отличиях DP-раскраски от предписанной раскраски”, Матем. тр., 21:2 (2018), 61–71  mathnet  crossref; A. Yu. Bernshteyn, A. V. Kostochka, “On differences between DP-coloring and list coloring”, Siberian Adv. Math., 29 (2019), 183–189  crossref
    3. A. Bernshteyn, A. Kostochka, “Sharp Dirac's theorem for DP-critical graphs”, J. Graph Theory, 88:3 (2018), 521–546  crossref  mathscinet  zmath  isi  scopus
    4. Z. Dvorak, L. Postle, “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8”, J. Comb. Theory Ser. B, 129 (2018), 38–54  crossref  mathscinet  zmath  isi  scopus
    5. T. Schweser, “DP-degree colorable hypergraphs”, Theor. Comput. Sci., 796 (2019), 196–206  crossref  mathscinet  zmath  isi  scopus
    6. P. Sittitrai, K. Nakprasit, “Sufficient conditions on planar graphs to have a relaxed DP-3-coloring”, Graphs Comb., 35:4 (2019), 837–845  crossref  mathscinet  zmath  isi  scopus
    7. S.-J. Kim, K. Ozeki, “A note on a Brooks' type theorem for DP-coloring”, J. Graph Theory, 91:2 (2019), 148–161  crossref  mathscinet  zmath  isi  scopus
    8. S.-J. Kim, X. Yu, “Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable”, Graphs Comb., 35:3 (2019), 707–718  crossref  mathscinet  zmath  isi  scopus
    9. Yu. Zhao, L. Miao, “Every planar graph with the distance of 5(-)-cycles at least 3 from each other is dp-3-colorable”, Mathematics, 8:11 (2020), 1920  crossref  mathscinet  isi  scopus
    10. S.-J. Kim, A. Kostochka, X. Li, X. Zhu, “On-line dp-coloring of graphs”, Discret Appl. Math., 285 (2020), 443–453  crossref  mathscinet  zmath  isi  scopus
    11. J.-B. Lv, J. Li, “The harmonic index of a graph and its dp-chromatic number”, Discret Appl. Math., 284 (2020), 611–615  crossref  mathscinet  zmath  isi  scopus
    12. K. M. Nakprasit, K. Nakprasit, “A generalization of some results on list coloring and dp-coloring”, Graphs Comb., 36:4 (2020), 1189–1201  crossref  mathscinet  zmath  isi  scopus
    13. P. Sittitrai, K. Nakprasit, “Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is dp-4-colorable”, Bull. Malays. Math. Sci. Soc., 43:3 (2020), 2271–2285  crossref  mathscinet  zmath  isi  scopus
    14. R. Liu, X. Li, K. Nakprasit, P. Sittitrai, G. Yu, “Dp-4-colorability of planar graphs without adjacent cycles of given length”, Discret Appl. Math., 277 (2020), 245–251  crossref  mathscinet  zmath  isi  scopus
  • Сибирский математический журнал Siberian Mathematical Journal
    Просмотров:
    Эта страница:160
    Полный текст:34
    Литература:19
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021