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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Ацикличное хроматическое число графа МакГи равно 3.

В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов. Ациклическим хроматическим числом 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.(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 цветов и менее.

Смотрите также[править | править вики-текст]

Замечания[править | править вики-текст]

Ссылки[править | править вики-текст]

  • M. I. Burstein Every 4-valent graph has an acyclic 5-coloring (in Russian) // Soobšč. Akad. Nauk Gruzin. SSR. — 1979. — Т. 93. — С. 21–24.
  • B. Grünbaum Acyclic colorings of planar graphs // Israel J. Math.. — 1973. — Т. 14. — С. 390–408. — DOI:10.1007/BF02764716
  • Thomas F. Coleman, Jin-Yi Cai The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices // SIAM. J. on Algebraic and Discrete Methods. — 1986. — Т. 7. — С. 221–235. — DOI:10.1137/0607026.
  • Guillaume Fertin, André Raspaud Acyclic coloring of graphs of maximum degree five: Nine colors are enough // Information Processing Letters. — 2008. — Т. 105. — С. 65–72. — DOI:10.1016/j.ipl.2007.08.022.
  • Kishore Yadav, Venkaiah Satish Acyclic coloring of graphs of maximum degree five: Eight colors are enough // ICGTA. — 2008. — Т. nil. — С. nil..
  • Kishore Yadav, Venkaiah Satish, Kishore Yadav, Kishore Kothapalli Acyclic coloring of graphs of maximum degree six: Twelve colors are enough // Electronic Notes in Discrete Mathematics. — 2009. — Т. 35. — С. 177–182. — DOI:10.1016/j.endm.2009.11.030.
  • Assefaw H. Gebremedhin, Arijit Tarafdar, Alex Pothen, Andrea Walther Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation // Informs Journal on Computing. — 2008. — Т. 21. — С. 209. — DOI:10.1287/ijoc.1080.0286.
  • 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.
  • San Skulrattanakulchai Acyclic colorings of subcubic graphs // Information Processing Letters. — 2004. — Т. 92. — С. 161–167. — DOI:10.1016/j.ipl.2004.08.002.
  • S. K. Stein B-sets and coloring problems // Bull. Amer. Math. Soc.. — 1970. — Т. 76. — С. 805–806. — DOI:10.1090/S0002-9904-1970-12559-9
  • S. K. Stein B-sets and planar maps // Pacific J. Math.. — 1971. — Т. 37. — С. 217–224.

Внешние ссылки[править | править вики-текст]