Хорошо окрашенный график
В теории графов , подразделе математики, хорошо раскрашенный граф — это неориентированный граф , для которого жадная раскраска использует одинаковое количество цветов независимо от порядка, в котором цвета выбираются для его вершин. То есть для этих графов хроматическое число (минимальное количество цветов) и число Гранди (максимальное количество жадно выбранных цветов) равны. [1]
Хорошо раскрашенные графы включают в себя полные графы и графы циклов нечетной длины (графы, которые образуют исключительные случаи теоремы Брукса ), а также полные двудольные графы и полные многодольные графы .
Простейшим примером плохо раскрашенного графа является четырехвершинный путь. Раскрашивание вершин в порядке следования использует два цвета, оптимальные для данного графа. Однако если сначала раскрасить концы пути (используя один и тот же цвет для каждого конца), то жадный алгоритм раскраски будет использовать три цвета для этого графа. Поскольку существует неоптимальный порядок вершин, путь не имеет хорошей окраски. [2] [3]
Граф хорошо раскрашен тогда и только тогда, когда в нем нет двух порядков вершин, для которых жадный алгоритм раскраски дает разное количество цветов. Следовательно, распознавание графов с плохой раскраской может выполняться в пределах класса сложности NP . С другой стороны, граф имеет число Гранди или больше тогда и только тогда, когда граф, полученный добавлением -вершинной клики, хорошо раскрашен. Следовательно, с помощью сокращения из проблемы чисел Гранди можно NP-полно проверить, существуют ли эти два порядка. Отсюда следует, что проверка правильности раскраски данного графа является ко-NP-полной. [1]
Граф наследственно хорошо раскрашен, если каждый индуцированный подграф хорошо раскрашен. Наследственно хорошо раскрашенные графы — это в точности кографы , графы, которые не имеют четырехвершинного пути в качестве индуцированного подграфа. [4]
