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

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

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



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






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


Матем. тр., 2018, том 21, номер 2, страницы 61–71 (Mi mt338)  

Об отличиях DP-раскраски от предписанной раскраски

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

a Университет штата Иллинойс, кафедра математики, Урбана, IL, США
b Институт математики им. С. Л. Соболева СО РАН, просп. Академика Коптюга, 4, Новосибирск, 630090 РОССИЯ

Аннотация: Дворжак и Постл [14] недавно ввели обобщение предписанной раскраски графов, которое мы называем DP-раскраской. Многие известные верхние оценки на предписанное хроматическое число графа также верны для его DP-хроматического числа, но в некоторых отношениях предписанные и DP-раскраски существенно отличаются друг от друга. В этой статье рассматриваются примеры таких различий. В частности, показано, что существуют плоские двудольные графы с DP-хроматическим числом $4$ и что реберное DP-хроматическое число $d$-регулярного графа, $d \geq 2$, не может быть меньше чем $d+1$.

Ключевые слова и фразы: предписанная раскраска графов, раскраска ребер, DP-раскраска графов.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-01-00353_a
16-01-00499_a
National Science Foundation DMS-1600592
Работа первого автора поддержана стипендией штата Иллинойс. Работа второго автора поддержана грантами РФФИ (коды проектов 18-01-00353A и 16-01-00499), а также грантом NSF DMS-1600592.


DOI: https://doi.org/10.17377/mattrudy.2018.21.202

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

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

Образец цитирования: А. Ю. Бернштейн, А. В. Косточка, “Об отличиях DP-раскраски от предписанной раскраски”, Матем. тр., 21:2 (2018), 61–71

Цитирование в формате AMSBIB
\RBibitem{BerKos18}
\by А.~Ю.~Бернштейн, А.~В.~Косточка
\paper Об отличиях DP-раскраски от предписанной раскраски
\jour Матем. тр.
\yr 2018
\vol 21
\issue 2
\pages 61--71
\mathnet{http://mi.mathnet.ru/mt338}
\crossref{https://doi.org/10.17377/mattrudy.2018.21.202}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mt338
  • http://mi.mathnet.ru/rus/mt/v21/i2/p61

    ОТПРАВИТЬ: 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
  • Математические труды Siberian Advances in Mathematics
    Просмотров:
    Эта страница:20
    Литература:3
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019