Предписанная раскраска

Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Одними из первых эту раскраску изучили Вадим Визинг и Пал Эрдёш, а также Рубин и Тейлор в 1970-х годах.

Определение

Если задан граф G и дано множество L (v) допустимых цветов для каждой вершины V (называемое списком), предписанная раскраска — это функция выбора, которая отображает каждую вершину V в список L (v). Как и в случае раскраски графов, предписанная раскраска предполагается правильной, это означает, что никакие две смежные вершины не получают тот же самый цвет. Граф называется k-выбираемым (или предписано-k-раскрашиваемым), если он имеет правильную предписанную раскраску независимо от способа распределения k цветов для каждой вершины. Число выбираемости (предписанная раскрашиваемость, или предписанное хроматическое число) ch (G) графа G — это наименьшее число k, такое, что G является k-выбираемым.

В общем случае, если дана функция f, назначающая положительное число f (v) для каждой вершины v, граф G называется f-выбираемым (или предписано-f-раскрашиваемым), если он имеет предписанную раскраску вне зависимости от того, как назначаются списки f (v) цветов для каждой вершины v. В частности, если $f(v)=k$ для всех вершин v, f - выбираемость соответствует k-выбираемости.

Примеры

Рассмотрим полный двудольный граф $G=K_{2,4}$, имеющий шесть вершин A, B, W, X, Y, Z, такой, что A и B соединены с каждой из вершин W, X, Y и Z и других рёбер нет. Как и для любого двудольного графа, обычное хроматическое число графа G равно 2 — можно раскрасить вершины A и B одним цветом, а остальные вершины (W, X, Y, Z) другим цветом, тогда никакие две смежные не будут иметь один цвет. С другой стороны, G имеет предписанное хроматическое число, большее 2, что показывает следующее построение: Назначаем вершинам A и B списки {красный, синий} и {зелёный, чёрный}. Назначим другим четырём вершинам списки {красный, зелёный}, {красный, чёрный}, {синий, зелёный} и {синий, чёрный}. Не имеет значения, какой выбор делается из списков для вершин A и B, потому что имеются некоторые другие вершины, для которых оба цвета в списке уже использованы. Таким образом, граф G не является 2-выбираемым.

С другой стороны, легко видеть, что G = 3 — выбор любых цветов для вершин A и B оставляет по меньшей мере один допустимый цвет для каждой оставшейся вершины.

Вариант предписанной раскраски для полного двудольного графа $K_{3,27}$ с тремя цветами на каждую вершину. Не имеет значения, какие цвета выбраны для трёх центральных вершин, одна из внешних 27 вершин не может быть выкрашена правильно, что показывает, что предписанное хроматическое число графа $K_{3,27}$ равно по меньшей мере четырём.

В общем случае, пусть q будет положительным целым числом, а G будет полным двудольным графом $K_{q,q^{q}}$. Пусть допустимые цвета представлены $q^{2}$ — различными двузначными числами в системе radix q (то есть, в q-ричной системе). Одной доле, а именно доле с q вершинами, пусть даны множества цветов s $\{i0,i1,i2,\dots \}$, в которых первые знаки равны для каждого выбора из q возможностей выбора цифры i. Другой доле графа с $q^{q}$ вершинами задаются цвета $\{0a,1b,2c,\dots \}$, для которых первая цифра различна для любого набора $(a,b,c,\dots )$ из q элементов. Иллюстрация показывает пример такого построения с q = 3.

Тогда G не имеет предписанной раскраски для L — не имеет значения, какой набор цветов выбран для вершин на меньшей стороне двудольного графа, этот выбор будет конфликтовать со всеми цветами для одной вершины на другой стороне двудольного графа. Например, если вершина с набором цветов {00,01} выкрашена в 01, а вершина с набором цветов {10,11} выкрашена в 10, то вершина с набором цветов {01,10} не может быть выкрашена правильно. Поэтому хроматическое число графа G равно по меньшей мере $q+1$.

Аналогично, если $n={\binom {2k-1}{k}}$, то полный двудольный граф $K_{n,n}$ не является k-выбираемым. Чтобы это показать, предположим, что в общей сложности доступно $2k-1$ цветов, так что на одной стороне двудольного графа каждая вершина имеет различные наборы из k цветов для каждой вершины. Тогда каждая сторона двудольного графа использует для раскраски по меньшей мере k цветов. В противном случае должна существовать вершина, в которой набор цветов отличен от $k-1$ используемых. Поскольку по меньшей мере k цветов используется на одной стороне и по меньшей мере k используется на другой, должен быть один цвет, который использован на обеих сторонах, но отсюда следует, что две смежные вершины имеют тот же цвет. В частности, коммунальный граф $K_{3,3}$ имеет предписанное хроматическое число, не меньшее трёх, а граф $K_{10,10}$ имеет предписанное хроматическое число, не меньшее четырёх.

Свойства

Для графа G, пусть $\chi (G)$ означает хроматическое число, а $\Delta (G)$ максимальную степень графа G. Число предписанной раскраски $ch(G)$ удовлетворяет следующим свойствам:

1. $ch(G)\geqslant \chi (G)$. Граф, позволяющий предписанную k-раскраску, должен, в частности, иметь предписанную раскраску, если любой вершине назначен один и тот же список из k цветов, что соответствует обычной k-раскраске;
2. $ch(G)$ не может быть ограничен в общем случае в терминах хроматического числа, то есть, не существует функции f, такой что $ch(G)\leqslant f(\chi (G))$ выполняется для любого графа G. В частности, как показано в примерах о двудольных графах, существуют графы с $\chi (G)=2$, для которых $ch(G)$ произвольно велико;
3. $ch(G)\leqslant \chi (G)\ln(n)$, где n является числом вершин графа G;
4. $ch(G)\leqslant \Delta (G)+1$;
5. $ch(G)\leqslant 5$, если G является планарным графом;
6. $ch(G)\leqslant 3$, если G является двудольным планарным графом.

Вычисление выбираемости и (a, b)-выбираемости

В литературе рассматриваются две алгоритмические задачи:

1. k-выбираемость: определить, является ли заданный граф k-выбираемым для заданного k;
2. (a, b)-выбираемость: определить, является ли заданный граф f-выбираемым для данной функции $f:V\to \{a,\dots ,b\}$.

Известно, что задача k-выбираемости в двудольных графах $\Pi _{2}^{p}$ — полна для любого $k\geqslant 3$ и то же самое верно для 4-выбираемости в планарных графах, 3-выбираемости в планарных графах без треугольников и (2, 3)-выбираемости в двудольных планарных графах. Для свободных от P₅ графов, то есть графов, в которых отсутствуют пути с 5 вершинами, k-выбираемость является фиксированно-параметрически разрешимой задачей.

Можно проверить, является ли граф 2-выбираемым: за линейное время путём последовательного удаления вершин с нулевой или единичной степенью, пока не получим 2-ядро графа, после чего такие удаления становятся невозможными. Исходный граф 2-выбираем тогда и только тогда, когда его 2-ядро либо является чётным циклом или тета-графом, образованным тремя путями с общими конечными точками, два пути длиной два, а третий путь может иметь любую чётную длину.

Приложения

Предписанная раскраска возникает в практических задачах, касающихся назначения частотных каналов.

См. также

• Предписанная раскраска рёбер

Литература для дальнейшего чтения

• Martin Aigner, Günter Ziegler. Chapter 34 Five-coloring plane graphs. // Proofs from THE BOOK. — 4th. — Berlin, New York: Springer-Verlag, 2009. — ISBN 978-3-642-00855-9.
• Рейнгард Дистель. Глава 5.4 «Предписанная раскраска» // Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X.