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

При решении задачи о предписанной раскраске плоских графов Дворжак и Постл ввели понятие DP-раскраски (они назвали его correspondence coloring). DP-раскраска графа $G$ сводит задачу поиска раскраски $G$ для заданного предписания $L$ к проблеме поиска “большого” независимого множества во вспомогательном графе $H(G,L)$ с множеством вершин $\{(v,c)\colon v\in V(G)\ \text{и}\ 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$-хроматических графах.