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

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

История

Дефектная окраска была введена почти одновременно Берром и Джейкобсоном, Харари и Джонсом и Коуэном, Коуэном и Вудаллом. Обзоры этой и связанных с ней раскрасок предоставлены Мариетджи Фрик. Коуэн, Коуэн и Вудалл сосредоточился на графах, встроенных в поверхности, и дал полную характеристику всех k и d, таких что каждая плоскость ( k , d )-раскрашиваема. А именно, не существует d такого , что каждый планарный граф (1, d )- или (2, d )-раскрашиваем; существуют плоские графы, которые не (3, 1)-раскрашиваемы, но каждый планарный граф (3, 2)-раскрашиваем. Вместе с (4, 0)-раскраской, подразумеваемой теоремой о четырех цветах , это решает проблему дефектного хроматического числа плоскости. Пох и Годдард показал, что любой планарный граф имеет специальную (3,2)-раскраску, в которой каждый цветовой класс представляет собой линейный лес, и это можно получить из более общего результата Вудала.Для общих поверхностей было показано, что для каждого рода $g\geq 0$, существует $k=k(g)$ такой, что каждый граф на поверхности рода $g$ является (4, k )-раскрашиваемым. Это было улучшено до (3, k )-раскраски Дэном Арчдиконом . Для общих графиков — результат Ласло Ловаша 1960-х годов, который много раз открывался заново. предоставляет алгоритм за время O(∆E) для дефектных графов раскраски максимальной степени ∆.

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

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

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

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

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

Для класса графов G дефектное хроматическое число G такое — это минимальное целое число k , что для некоторого целого числа d каждый граф в G является ( k , d )-раскрашиваемым. Например, дефектное хроматическое число класса плоских графов равно 3, поскольку каждый планарный граф (3,2)-раскрашиваем и для каждого целого числа d существует планарный граф, не (2, d )-раскрашиваемый.

Несоответствие вершины

Пусть c — вершинная раскраска графа G . Несоответствие вершины v группы G относительно раскраски c — это количество соседей вершины 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}$

Характеристики

• Достаточно рассмотреть связные графы, поскольку граф G ( k , d )-раскрашивается тогда и только тогда, когда каждая компонента связности G ( k , d ) -раскрашиваема.
• С точки зрения теории графов, каждый класс цвета в правильной раскраске вершин образует независимое множество , в то время как каждый класс цвета в дефектной раскраске образует подграф степени не выше d .
• Если граф ( k , d )-раскрашиваем, то он ( k' , d' )-раскрашиваем для каждой пары ( k' , d' ) такой, что k' ≥ k и d' ≥ 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)$- раскрашиваемый.

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

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

Приложения

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

Ссылки

• Итон, Нэнси Дж.; Халл, Томас (1999), «Дефектные списковые раскраски плоских графов», Bull. Инст. Комбинировать. Приложение , 25 : 79–87, CiteSeerX   10.1.1.91.4722 .
• Уильям, В.; Халл, Томас (2002), «Дефектная круговая раскраска», австр. Дж. Комбинаторика , 26 : 21–32, CiteSeerX   10.1.1.91.4722 .
• Фрик, Мариетджи; Хеннинг, Майкл (март 1994 г.), «Экстремальные результаты о дефектных раскрасках графов», Discrete Mathematics , 126 (1–3): 151–158, doi : 10.1016/0012-365X(94)90260-7
• Эл Джей Коуэн; В. Годдард; CE Jesurum (5 января 1997 г.), «Раскраска с дефектом» , SODA '97, Материалы восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 548–557, ISBN  9780898713909
• Эл Джей Коуэн; Р. Х. Коуэн; Д. Р. Вудалл (3 октября 2006 г.), «Дефектные раскраски графов на поверхностях: разбиения на подграфы ограниченной валентности», Journal of Graph Theory , 10 (2): 187–195, doi : 10.1002/jgt.3190100207
• Архидьякон, Дэн (1987), «Заметка о дефектных раскрасках графов на поверхностях», Journal of Graph Theory , 11 (4): 517–519, doi : 10.1002/jgt.3190110408
• По, К.С. (март 1990 г.), «О линейной вершинно-древесности плоского графа», Journal of Graph Theory , 14 (1): 73–75, doi : 10.1002/jgt.3190140108
• Годдард, Уэйн (7 августа 1991 г.), «Ациклические раскраски плоских графов», Discrete Mathematics , 91 (1): 91–94, doi : 10.1016/0012-365X(91)90166-Y
• Бородин О.В.; Косточка А.В. (октябрь – декабрь 1977 г.), «О верхней границе хроматического числа графа в зависимости от степени и плотности графа», Журнал комбинаторной теории , серия B, 23 (2–3): 247–250, doi : 10.1016/0095-8956(77)90037-5
• Лоуренс, Джим (1978), «Покрытие множества вершин графа подграфами меньшей степени», Discrete Mathematics , 21 (1): 61–68, doi : 10.1016/0012-365X(78)90147-4
• Анджелини, Патрицио; Бекос, Майкл; Де Лука, Феличе; Дидимо, Уолтер; Кауфманн, Майкл; Кобуров, Стивен; Монтеккиани, Фабрицио; Рафтопулу, Хризанти; Роселли, Винченцо; Симвонис, Антониос (2017), «Раскраска вершин с дефектами», Журнал графовых алгоритмов и приложений , 21 (3): 313–340, doi : 10.7155/jgaa.00418