Бернштейн А. Ю., Косточка А. В., Пронь С. П.
О DP-раскраске графов и мультиграфов

При решении задачи о предписанной раскраске плоских графов Дворжак и Постл ввели понятие DP-раскраски (они назвали его 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_{DP}(G)$ напоминают свойства предписанного хроматического числа $\chi_{\ell}(G)$, но некоторые отличия довольно существенны. Всегда $\chi_{DP}(G)\geq \chi_{\ell}(G)$. Целью настоящей работы является введение DP-раскраски для мультиграфов и доказательство аналога результата O. B. Бородина и Эрдсша — Рубина — Тейлора, характеризующего мультиграфы, которые не допускают DP-раскрасок для некоторых степенных предписаний. Из этого результата следует аналог для DP-раскраски теоремы Галлаи о минимальном числе ребер в критических $k$-хроматических графах.

A. Yu. Bernshteyn, A. V. Kostochka, S. P. Pron
On DP-coloring of graphs and multigraphs

While solving a question on the list coloring of planar graphs, Dvorák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph $G$ reduces the problem of finding a coloring of $G$ from a given list $L$ to the problem of finding a “large” independent set in the auxiliary graph $H(G,L)$ with vertex set $\{(v,c): v\in V(G) \text{ and } {c\in L(v)} \}$. It is similar to the old reduction by Plesnevic and Vizing of the $k$-coloring problem to the problem of finding an independent set of size $|V(G)|$ in the Cartesian product $G\square K_k$, but DP-coloring seems more promising and useful than the Plesnevic–Vizing reduction. Some properties of the DP-chromatic number $\chi_{DP}(G)$ resemble the properties of the list chromatic number $\chi_{\ell}(G)$ but some differ quite a lot. It is always the case that $\chi_{DP}(G)\geq \chi_{\ell}(G)$. The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erdos–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai’s Theorem on the minimum number of edges in $n$-vertex graphs critical with respect to DP-coloring.

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

Полный текст статьи / Full texts:

• PDF file
• PostScript file