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

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