В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов. Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G.
Ациклическая раскраска часто связывается с графами на поверхностях, не являющихся плоскостями.
Верхние границы 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. A(G) ≤ 12 если Δ(G) = 6.
Вехой в изучении ациклической раскраски является следующий положительный ответ на гипотезу Грюнбаума:
Теорема. (Borodin 1979) A(G) ≤ 5 если G планарен.
Грюнбаум (1973) ввёл ациклическую раскраску и ациклическое хроматическое число и высказал гипотезу, которая и была доказана Бородиным. На доказательство у Бородина ушло несколько лет старательной проверки 450 конфигураций. Одним из следствий этой теоремы является то, что любой планарный граф можно разложить на независимое множество и два леса. (Stein 1970, 1971)
Алгоритмы и сложность Задача определения, выполняется ли A(G) ≤ 3, является NP-полной (Kostochka 1978). Коулман и Цай показали, что задача остаётся NP-полной даже для двудольных графов.
Гебремедхин и др. продемонстрировали, что любая правильная вершинная раскраска хордального графа является ациклической раскраской. Поскольку для хордальных графов можно найти оптимальную раскраску за время O(n+m), то же самое верно и для ациклической раскраски на этом классе графов.
Линейный по времени алгоритм для ациклической раскраски графа максимальной степени ≤ 3 в 4 цвета или меньше представлен Скулраттанакулчаем . Ядав и Сатиш описывают линейный по времени алгоритм ациклической раскраски графа с максимальной степенью ≤ 5 при использовании 8 цветов и менее, а также алгоритм раскраски графа максимальной степени ≤ 6 при использовании 12 цветов и менее.
См. также Звёздная раскраска
Замечания
Ссылки
.
.
.
. .
.
Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7. Kostochka, A. V. (1978). Upper bounds of chromatic functions of graphs (in Russian). Doctoral thesis, Novosibirsk.
.
Внешние ссылки Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008. Acyclic Coloring of Graphs of Maximum Degree ∆, talk slides presented by G. Fertin and A. Raspaud at EUROCOMB 05, Berlin, 2005.
Категория:Теория графов Категория:Раскраска графа