Хорошо раскрашиваемый граф — это неориентированный граф, для которого жадная раскраска использует одно и то же число цветов, независимо от порядка выбора вершин. То есть, для этих графов хроматическое число (минимальное число цветов) и число Гранди (максимальное число выбранных жадным алгоритмом цветов) равны.
Примеры Хорошо раскрашиваемые графы включают полные графы и циклы нечётной длины (графы, образующие исключения теоремы Брукса), а также полные двудольные графы и полные многодольные графы.
Простейшим примером графа, не являющегося хорошо раскрашиваемым, служит путь из четырёх вершин. Раскраска вершин в порядке следования пути потребует два цвета — оптимальное число для этого графа. Однако, раскраска сначала концов этого графа (используя один цвет для обоих концов) заставляет жадный алгоритм использовать три цвета. Поскольку существует неоптимальный порядок выбора вершин, путь не является хорошо раскрашиваемым.
Сложность Граф хорошо раскрашиваем тогда и только тогда, когда не имеет двух упорядочиваний вершин, при которых жадный алгоритм требует различное число чветов. Поэтому распознавание, не является ли граф хорошо раскрашиваемым, может быть выполнено в классе сложности NP. С другой стороны, граф имеет число Гранди или больше тогда и только тогда, когда граф, полученный из путём добавления -вершинной клики хорошо раскрашиваем. Поэтому, путём сведения от задачи вычисления числа Гранди, проверка существования двух таких порядков NP-полна. Отсюда следует, что проверка, является ли данный граф хорошо раскрашиваевым, co-NP-полная задача.
Связанные свойства Граф является наследственно хорошо раскрашиваемым, если любой порождённый подграф является хорошо раскрашиваемым — это в точности кографы (они не имеют в качестве порождённых подграфов пути с четырьмя вершинами).
Примечания
Категория:Раскраска графа Категория:Семейства графов