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

Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Одними из первых эту раскраску изучили Вадим Визинг и Пал Эрдёш, а также Рубин и Тейлор^[1] в 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. В частности, если ${\displaystyle f(v)=k}$ для всех вершин v, f - выбираемость соответствует k-выбираемости.

Примеры

Рассмотрим полный двудольный граф ${\displaystyle 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 оставляет по меньшей мере один допустимый цвет для каждой оставшейся вершины.

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

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

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

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

Свойства

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

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

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

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

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

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

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

Приложения

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

См. также

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

Примечания

1. Jensen, Toft, 1995, с. 18–21.
2. Gravier, 1996, с. 299–302.
3. Erdős, Rubin, Taylor, 1979, с. 125–157.
4. Eaton, 2003.
5. Визинг, 1976, с. 3–10.
6. Thomassen, 1994, с. 180–181.
7. Alon, Tarsi, 1992, с. 125–134.
8. Gutner, 1996, с. 119–130.
9. Gutner, Tarsi, 2009, с. 2260–2270.
10. Heggernes, Golovach, 2009, с. 382–391.
11. Wang, Liu, 2005, с. 690–694.
12. Garg, Papatriantafilou, Tsigas, 1996, с. 18–25.

Литература

• Tommy R. Jensen, Bjarne Toft. 1.9 List coloring // Graph coloring problems. — New York: Wiley-Interscience, 1995. — ISBN 0-471-02865-7.
• Sylvain Gravier. A Hajós-like theorem for list coloring // Discrete Mathematics. — 1996. — Т. 152, вып. 1—3. — С. 299—302. — doi:10.1016/0012-365X(95)00350-6.
• Erdős P., Rubin A. L., Taylor H. Choosability in graphs // Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata. — 1979. — Т. 26. — (Congressus Numerantium). Архивная копия от 9 марта 2016 на Wayback Machine
• Nancy Eaton. On two short proofs about list coloring - Part 1. — 2003. Архивировано 29 августа 2017 года.
• Nancy Eaton. On two short proofs about list coloring - Part 2. — 2003. Архивировано 30 августа 2017 года.
• Визинг В. Г. Раскраска вершин графа в предписанные цвета // Мето-ды дискрет. анализа в теории кодов и схем. Сб. науч. Тр.. — Новосибирск: Ин-т математики СО АН СССР, 1976. — Вып. 29. — С. 3—10.
• Carsten Thomassen. Every planar graph is 5-choosable // Journal of Combinatorial Theory, Series B. — 1994. — Т. 62. — doi:10.1006/jctb.1994.1062.
• Noga Alon, Michael Tarsi. Colorings and orientations of graphs // Combinatorica. — 1992. — Т. 12. — doi:10.1007/BF01204715.
• Shai Gutner. The complexity of planar graph choosability // Discrete Mathematics. — 1996. — Т. 159, вып. 1. — С. 119—130. — doi:10.1016/0012-365X(95)00104-5. — arXiv:0802.2668.
• Shai Gutner, Michael Tarsi. Some results on (a:b)-choosability // Discrete Mathematics. — 2009. — Т. 309, вып. 8. — doi:10.1016/j.disc.2008.04.061.
• Pinar Heggernes, Petr Golovach. Choosability of P₅-free graphs // Mathematical Foundations of Computer Science. — Springer-Verlag, 2009. — Т. 5734. — С. 382–391. — (Lecture Notes on Computer Science).
• Wei Wang, Xin Liu. List-coloring based channel allocation for open-spectrum wireless networks // 2005 IEEE 62nd Vehicular Technology Conference (VTC 2005-Fall). — 2005. — Т. 1. — С. 690–694. — doi:10.1109/VETECF.2005.1558001.
• Garg N., Papatriantafilou M., Tsigas P. Distributed list coloring: how to dynamically allocate frequencies to mobile base stations // Eighth IEEE Symposium on Parallel and Distributed Processing. — 1996. — С. 18–25. — doi:10.1109/SPDP.1996.570312.

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

• 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.