СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

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