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

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

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

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

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

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

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

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

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

Пример

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

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

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

Любой внешнепланарный граф (2,2)-раскрашиваем Доказательство: Пусть будет связным внешнепланарным графом. Пусть будет произвольной вершиной графа . Пусть будет набором вершин графа которые находятся на расстоянии от . Пусть будет , подграфом, порождённым набором вершин . Предположим, что содержит вершину степени 3 или более, тогда он содержит в качестве подграфа. Тогда мы стягиваем все рёбра графа , чтобы получить новый граф . Следует заметить, что графа связен, поскольку любая вершина в смежна вершине в . Следовательно, стягиванием всех рёбер, упомянутых выше, мы получим граф , такой что подграф графа заменяется одной вершиной, которая смежна всем вершинам в . Тогда граф содержит в качестве подграфа. Но любой подграф внешнепланарного графа внешнепланарен, и любой граф, полученный стягиванием рёбер внешнепланарного графа, является внешнепланарным. Из этого следует, что внешнепланарен, чего не может быть. Следовательно, никакой из графов не содержит вершин степени 3 и выше, откуда следует, что (k, 2)-раскрашиваем.

Следует также заметить, что никакая вершина из не смежна с какой-либо вершиной или , следовательно вершины могут быть выкрашены в синий цвет, если нечётно, или в красный цвет, если чётно. Следовательно, мы получили (2,2)-раскраску графа .

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

Графы без полных миноров Для любого целого существует целое , такое что любой граф без миноров является -раскрашиваемым.

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

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

Примечания

Литература

Категория:Раскраска графа