Ациклическая раскраска графа

В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов. Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G.

Ацикличное хроматическое число графа МакГи равно 3.

Ациклическая раскраска часто связывается с графами на поверхностях, не являющихся плоскостями.

Верхние границы

A(G) ≤ 2 тогда и только тогда, когда G не имеет циклов.

Границы A(G) в терминах максимальной степени Δ(G) графа G включают следующие:

• A(G) ≤ 4 если Δ(G) = 3. (Grünbaum 1973)
• A(G) ≤ 5 если Δ(G) = 4. (Burstein 1979)
• A(G) ≤ 8 если Δ(G) = 5.(Yadav, Satish 2008)
• A(G) ≤ 12 если Δ(G) = 6.(Yadav, Satish 2009)

Вехой в изучении ациклической раскраски является следующий положительный ответ на гипотезу Грюнбаума:

Теорема. (Borodin 1979)

A(G) ≤ 5 если G планарен.

Грюнбаум (1973) ввёл ациклическую раскраску и ациклическое хроматическое число и высказал гипотезу, которая и была доказана Бородиным. На доказательство у Бородина ушло несколько лет старательной проверки 450 конфигураций. Одним из следствий этой теоремы является то, что любой планарный граф можно разложить на независимое множество и два леса. (Stein 1970, 1971)

Алгоритмы и сложность

Задача определения, выполняется ли A(G) ≤ 3, является NP-полной (Kostochka 1978). Коулман и Цай (Coleman, Cai 1986) показали, что задача остаётся NP-полной даже для двудольных графов.

Гебремедхин и др. (Gebremedhin, Tarafdar, Pothen, Walther 2008) продемонстрировали, что любая правильная вершинная раскраска хордального графа является ациклической раскраской. Поскольку для хордальных графов можно найти оптимальную раскраску за время O(n+m), то же самое верно и для ациклической раскраски на этом классе графов.

Линейный по времени алгоритм для ациклической раскраски графа максимальной степени ≤ 3 в 4 цвета или меньше представлена Скулраттанакулчаем (Skulrattanakulchai 2004). Ядав и Сатиш (Yadav, Satish 2008) описывают линейный по времени алгоритм ациклической раскраски графа с максимальной степенью ≤ 5 при использовании 8 цветов и менее, а также алгоритм раскраски графа максимальной степени ≤ 6 при использовании 12 цветов и менее.

См. также

• Звёздная раскраска