Дефектная раскраска

Дефектная раскраска — это вариант правильной раскраски вершин. В правильной раскраске вершин вершины раскрашиваются так, что никакая из смежных вершин не имеют одного цвета. При дефектной раскраске, с другой стороны, вершинам разрешено в известной мере иметь соседей того же цвета.

История

Дефектную раскраску предложили почти одновременно Бурр и Джексон, Харари и Джонс, Ковины и Вудал. Обзор этих и связанных раскрасок дала Марики Фрик. Ковины (Л. И Р.) и Вудал сфокусировались на графах, вложенных в поверхности и дали полное описание всех k и d, таких что любой планарный граф (k, d)-раскрашиваем. А именно, не существует d таких, что любой планарный граф (1, d)- или (2, d)-раскрашиваем. Существуют планарные графы, которые не (3, 1)-раскрашиваемы, но любой планарный граф имеет (3, 2)-раскраску. Вместе с (4, 0)-раскраской, вытекающей из теоремы о четырёх красках, это решает задачу о дефектном хроматическом числе для плоскости. Пох и Годдар показали, что любой планарный граф имеет специальную (3,2)-раскраску, в которой каждый класс цвета является линейным лесом, и это можно получить из более общего результата Вудала.

Для поверхностей общего вида было показано, что для любого рода $g\geqslant 0$ существует число $k=k(g)$ такое, что любой граф на поверхности рода $g$ (4, k)-раскрашиваем. Этот результат улучшил до (3, k)-раскрашиваемости Дэн Арчдикон.

Для графов общего вида результат Ласло Ловаса 1960-х годов, который был переоткрыт много раз, даёт алгоритм со временем работы $O(\Delta E)$ для дефектной раскраски графов с максимальной степенью $\Delta$.

Определения и терминология

Дефектная раскраска

$(k,d)$-раскраска графа G — это раскраска вершин графа в k цветов так, что каждая вершина v имеет максимум d соседей того же цвета, что и вершина v. Мы считаем k положительным целым числом (бессмысленно рассматривать случай с нулевым числом цветов, k=0), а d считаем неотрицательным целым. Тогда (k, 0)-раскраска эквивалентна правильной раскраске вершин.

d-дефектное хроматическое число

Минимальное число цветов k, требующихся для получения (k, d)-раскраски графа G, называется d-дефектным хроматическим числом, $\chi _{d}(G)$.

Неправильность вершины

Пусть c будет раскраской вершин графа G. Неправильностью вершины v графа G, это число соседей вершин v, которые имеют тот же цвет, что и v. Если неправильность вершины v равна 0, тогда говорят, что вершина v правильно раскрашена.

Неправильность раскраски вершины

Пусть c будет раскраской вершин графа G. Неправильность раскраски c — это максимум неправильностей всех вершин графа G. Следовательно, неправильность правильной раскраски вершин равна 0.

Пример

Пример дефектной раскраски цикла с пятью вершинами, когда d=0, 1, 2

Пример дефектной раскраски цикла с пятью вершинами $C_{5}$ показан на рисунке. Первый пятиугольник является примером правильной раскраски, или (k, 0)-раскраски. Второй пятиугольник является примером (k, 1)-раскраски, а третий — примером (k, 2)-раскраски. Заметьте, что

$\chi _{0}(C_{5})=\chi (C_{5})=3$

$\chi _{1}(C_{5})=3$

$\chi _{2}(C_{n})=1;\forall n\in \mathbb {N}$

Свойства

• В терминах теории графов, каждый класс правильной раскраски вершин образует независимое множество, в то время как каждый класс дефектной раскраски образует подграф степени, не превосходящей d.
• Если граф (k, d)-раскрашиваем, то он (k′, d′)-раскрашиваем для каждой пары (k′, d′) такой что $k'\geqslant k$ и $d'\geqslant d$.

Некоторые результаты

Любой внешнепланарный граф (2,2)-раскрашиваем

Доказательство: Пусть $G$ будет связным внешнепланарным графом. Пусть $v_{0}$ будет произвольной вершиной графа $G$. Пусть $V_{i}$ будет набором вершин графа $G$ которые находятся на расстоянии $i$ от $v_{0}$. Пусть $G_{i}$ будет $\langle V_{i}\rangle$, подграфом, порождённым набором вершин $V_{i}$. Предположим, что $G_{i}$ содержит вершину степени 3 или более, тогда он содержит $K_{1,3}$ в качестве подграфа. Тогда мы стягиваем все рёбра графа $V_{0}\cup V_{1}\cup ...\cup V_{i-1}$, чтобы получить новый граф $G'$. Следует заметить, что $\langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle$ графа $G'$ связен, поскольку любая вершина в $V_{i}$ смежна вершине в $V_{i-1}$. Следовательно, стягиванием всех рёбер, упомянутых выше, мы получим граф $G'$, такой что подграф $\langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle$ графа $G'$ заменяется одной вершиной, которая смежна всем вершинам в $V_{i}$. Тогда граф $G'$ содержит $K_{2,3}$ в качестве подграфа. Но любой подграф внешнепланарного графа внешнепланарен, и любой граф, полученный стягиванием рёбер внешнепланарного графа, является внешнепланарным. Из этого следует, что $K_{2,3}$ внешнепланарен, чего не может быть. Следовательно, никакой из графов $G_{i}$ не содержит вершин степени 3 и выше, откуда следует, что $G$ (k, 2)-раскрашиваем.

Следует также заметить, что никакая вершина из $V_{i}$ не смежна с какой-либо вершиной $V_{i-1}$ или $V_{i+1},i\geqslant 1$, следовательно вершины $V_{i}$ могут быть выкрашены в синий цвет, если $i$ нечётно, или в красный цвет, если чётно. Следовательно, мы получили (2,2)-раскраску графа $G$.

Следствие: Любой планарный граф (4,2)-раскрашиваем. Это следует из того, что если $G$ планарен, то любой $G_{i}$ (как выше) внешнепланарен. Следовательно, любой $G_{i}$ (2,2)-раскрашиваем. Следовательно, каждая вершина $V_{i}$ может быть раскрашена в красный или синий цвет, если $i$ чётно и в зелёный и жёлтый цвет, если $i$ нечётно, что даёт (4,2)-раскраску графа $G$.

Графы без полных миноров

Для любого целого $t$ существует целое $N$, такое что любой граф $G$ без $K_{t}$ миноров является $(t-1,N)$-раскрашиваемым.

Вычислительная сложность

Дефектная раскраска вычислительно трудна. Задача определения, позволяет ли данный граф $G$ (3,1)-раскраску NP-полна, даже в случае, когда $G$ имеет максимальную степень вершины 6 или когда он планарен и имеет максимальную степень вершин 7.

Приложения

Пример приложения дефектной раскраски — задача расписания, в которой вершины представляют работы (скажем, пользователи компьютерной системы), а рёбра представляют конфликты (необходимость доступа к одним и тем же файлам). Разрешение дефекта означает допустимость некоторого порога конфликта — каждый пользователь может, скажем, принять максимально допустимое замедление, вызванное извлечением данных из двух конфликтных файлов, но не более.

Литература

• Marietjie Frick. A Survey of (m,k)-Colorings. — Annals of Discrete Mathematics. — 1993. — Т. 55. — ISBN 9780444894410. — doi:10.1016/S0167-5060(08)70374-1.
• Poh K. S. On the linear vertex-arboricity of a planar graph // Journal of Graph Theory. — 1990. — Март (т. 14, вып. 1). — doi:10.1002/jgt.3190140108.
• Wayne Goddard. Acyclic colorings of planar graphs // Journal Discrete Mathematics. — 1991. — Август (т. 91, вып. 1). — doi:10.1016/0012-365X(91)90166-Y.
• Dan Archdeacon. A note on defective colorings of graphs in surfaces // Journal of Graph Theory. — 1987. — Т. 11, вып. 4. — doi:10.1002/jgt.3190110408.
• Claudio Bernardi. On a theorem about vertex colorings of graphs // Discrete Mathematics. — 1987. — Март (т. 64, вып. 1). — doi:10.1016/0012-365X(87)90243-3.
• Borodin O.V, Kostochka A.V. On an upper bound of a graph's chromatic number, depending on the graph's degree and density // Journal of Combinatorial Theory, Series B. — 1977. — Oct–Dec (т. 23, вып. 2–3). — doi:10.1016/0095-8956(77)90037-5.
• Jim Lawrence. Covering the vertex set of a graph with subgraphs of smaller degree // Discrete Mathematics. — 1978. — Т. 21, вып. 1. — doi:10.1016/0012-365X(78)90147-4.
• Cowen L., Goddard W., Jesurum C. E. Coloring with defect // In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97, New Orleans, Louisiana, United States, January 05–07, 1997). — Philadelphia, PA: Society for Industrial and Applied Mathematics, 1997.
• Cowen L., Goddard W., Jesurum C. E. Defective coloring revisited // J. Graph Theory. — 1997. — Т. 24, вып. 3. — doi:10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T.
• Marietjie Frick, Michael Henning. Extremal results on defective colorings of graphs // Discrete Mathematics. — 1994. — Март (т. 126, вып. 1–3). — doi:10.1016/0012-365X(94)90260-7.
• Cowen L. J., Cowen R. H., Woodall D. R. Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency // Journal of Graph Theory. — 2006. — Октябрь (т. 10, вып. 2). — doi:10.1002/jgt.3190100207.
• Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, Paul Seymour. A Relative of Hadwiger's Conjecture // SIAM Journal on Discrete Mathematics. — 2015. — Т. 29. — doi:10.1137/141002177. — arXiv:1407.5236.
• Patrizio Angelini, Michael Bekos, Felice De Luca, Walter Didimo, Michael Kaufmann, Stephen Kobourov, Fabrizio Montecchiani, Chrysanthi Raftopoulou, Vincenzo Roselli, Antonios Symvonis. Vertex-Coloring with Defects // Journal of Graph Algorithms and Applications. — 2017. — Т. 21, вып. 3. — С. 313–340. — doi:10.7155/jgaa.00418.
• Nancy J. Eaton, Thomas Hull. Defective list colorings of planar graphs // Bull. Inst. Combin. Appl. — 1999. — Т. 25. — С. 79–87.
• William W., Thomas Hull. Defective Circular Coloring // Austr. J. Combinatorics. — 2002. — Т. 26. — С. 21–32.