Дефектная раскраска
Дефектная раскраска — это вариант правильной раскраски вершин. В правильной раскраске вершин вершины раскрашиваются так, что никакая из смежных вершин не имеют одного цвета. При дефектной раскраске, с другой стороны, вершинам разрешено в известной мере иметь соседей того же цвета.
История
Дефектную раскраску предложили почти одновременно Бурр и Джексон, Харари и Джонс, Ковины и ВудалШаблон:Sfn. Обзор этих и связанных раскрасок дала Марики ФрикШаблон:Sfn. Ковины (Л. И Р.) и ВудалШаблон:Sfn сфокусировались на графах, вложенных в поверхности и дали полное описание всех k и d, таких что любой планарный граф (k, d)-раскрашиваем. А именно, не существует d таких, что любой планарный граф (1, d)- или (2, d)-раскрашиваем. Существуют планарные графы, которые не (3, 1)-раскрашиваемы, но любой планарный граф имеет (3, 2)-раскраску. Вместе с (4, 0)-раскраской, вытекающей из теоремы о четырёх красках, это решает задачу о дефектном хроматическом числе для плоскости. ПохШаблон:Sfn и ГоддарШаблон:Sfn показали, что любой планарный граф имеет специальную (3,2)-раскраску, в которой каждый класс цвета является линейным лесом, и это можно получить из более общего результата Вудала.
Для поверхностей общего вида было показано, что для любого рода существует число такое, что любой граф на поверхности рода (4, k)-раскрашиваемШаблон:Sfn. Этот результат улучшил до (3, k)-раскрашиваемости Дэн АрчдиконШаблон:Sfn.
Для графов общего вида результат Ласло Ловаса 1960-х годов, который был переоткрыт много разШаблон:SfnШаблон:SfnШаблон:Sfn, даёт алгоритм со временем работы для дефектной раскраски графов с максимальной степенью .
Определения и терминология
Дефектная раскраска
-раскраска графа G — это раскраска вершин графа в k цветов так, что каждая вершина v имеет максимум d соседей того же цвета, что и вершина v. Мы считаем k положительным целым числом (бессмысленно рассматривать случай с нулевым числом цветов, k=0), а d считаем неотрицательным целым. Тогда (k, 0)-раскраска эквивалентна правильной раскраске вершинШаблон:Sfn.
d-дефектное хроматическое число
Минимальное число цветов k, требующихся для получения (k, d)-раскраски графа G, называется d-дефектным хроматическим числом, Шаблон:Sfn.
Неправильность вершины
Пусть c будет раскраской вершин графа G. Неправильностью вершины v графа G, это число соседей вершин v, которые имеют тот же цвет, что и v. Если неправильность вершины v равна 0, тогда говорят, что вершина v правильно раскрашенаШаблон:Sfn.
Неправильность раскраски вершины
Пусть c будет раскраской вершин графа G. Неправильность раскраски c — это максимум неправильностей всех вершин графа G. Следовательно, неправильность правильной раскраски вершин равна 0Шаблон:Sfn.
Пример
Пример дефектной раскраски цикла с пятью вершинами показан на рисунке. Первый пятиугольник является примером правильной раскраски, или (k, 0)-раскраски. Второй пятиугольник является примером (k, 1)-раскраски, а третий — примером (k, 2)-раскраски. Заметьте, что
Свойства
- В терминах теории графов, каждый класс правильной раскраски вершин образует независимое множество, в то время как каждый класс дефектной раскраски образует подграф степени, не превосходящей dШаблон:Sfn.
- Если граф (k, d)-раскрашиваем, то он (k′, d′)-раскрашиваем для каждой пары (k′, d′) такой что и Шаблон:Sfn.
Некоторые результаты
Любой внешнепланарный граф (2,2)-раскрашиваем
Доказательство: Пусть будет связным внешнепланарным графом. Пусть будет произвольной вершиной графа . Пусть будет набором вершин графа которые находятся на расстоянии от . Пусть будет , подграфом, порождённым набором вершин . Предположим, что содержит вершину степени 3 или более, тогда он содержит в качестве подграфа. Тогда мы стягиваем все рёбра графа , чтобы получить новый граф . Следует заметить, что графа связен, поскольку любая вершина в смежна вершине в . Следовательно, стягиванием всех рёбер, упомянутых выше, мы получим граф , такой что подграф графа заменяется одной вершиной, которая смежна всем вершинам в . Тогда граф содержит в качестве подграфа. Но любой подграф внешнепланарного графа внешнепланарен, и любой граф, полученный стягиванием рёбер внешнепланарного графа, является внешнепланарным. Из этого следует, что внешнепланарен, чего не может быть. Следовательно, никакой из графов не содержит вершин степени 3 и выше, откуда следует, что (k, 2)-раскрашиваем.
Следует также заметить, что никакая вершина из не смежна с какой-либо вершиной или , следовательно вершины могут быть выкрашены в синий цвет, если нечётно, или в красный цвет, если чётно. Следовательно, мы получили (2,2)-раскраску графа Шаблон:Sfn.
Следствие: Любой планарный граф (4,2)-раскрашиваем. Это следует из того, что если планарен, то любой (как выше) внешнепланарен. Следовательно, любой (2,2)-раскрашиваем. Следовательно, каждая вершина может быть раскрашена в красный или синий цвет, если чётно и в зелёный и жёлтый цвет, если нечётно, что даёт (4,2)-раскраску графа .
Графы без полных миноров
Для любого целого существует целое , такое что любой граф без миноров является -раскрашиваемымШаблон:Sfn.
Вычислительная сложность
Дефектная раскраска вычислительно трудна. Задача определения, позволяет ли данный граф (3,1)-раскраску NP-полна, даже в случае, когда имеет максимальную степень вершины 6 или когда он планарен и имеет максимальную степень вершин 7Шаблон:Sfn.
Приложения
Пример приложения дефектной раскраски — задача расписания, в которой вершины представляют работы (скажем, пользователи компьютерной системы), а рёбра представляют конфликты (необходимость доступа к одним и тем же файлам). Разрешение дефекта означает допустимость некоторого порога конфликта — каждый пользователь может, скажем, принять максимально допустимое замедление, вызванное извлечением данных из двух конфликтных файлов, но не болееШаблон:Sfn.