Ациклическая окраска

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

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

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

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

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

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

• A( G ) ≤ 4, если Δ( G ) = 3. ( Грюнбаум, 1973 )
• A( G ) ≤ 5, если ∆( G ) = 4. ( Бурштейн, 1979 )
• A( G ) ≤ 7 if Δ( G ) = 5. ( Kostochka & Stocker 2011 )
• A( G ) ≤ 12, если Δ( G ) = 6. ( Варагани и др., 2009 )

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

Теорема ( Бородин, 1979 г. ) A( G ) ≤ 5, если G — планарный граф.

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

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

NP -полно определить, является ли A( G ) ≤ 3. ( Косточка 1978 )

Коулман и Кай (1986) показали, что вариант решения проблемы является NP-полным, даже если G — двудольный граф .

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

Алгоритм с линейным временем для ациклической окраски графа максимальной степени ≤ 3 с использованием 4 или меньше цветов был предложен Skulrattanakulchai (2004) .

См. также

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

Ссылки

• Бородин О.В. (1979), "Об ациклических раскрасках плоских графов", Дискретная математика , 25 (3): 211–236, doi : 10.1016/0012-365X(79)90077-3 .
• Бурштейн М.И. (1979), "Каждый 4-валентный граф имеет ациклическую 5-раскраску (на русском языке)", Сообщ. Акад. Наук Грузин. ССР , 93 : 21–24.
• Грюнбаум, Б. (1973), «Ациклические раскраски плоских графов», Израильский математический журнал , 14 (4): 390–408, doi : 10.1007/BF02764716 , S2CID   122808877
• Коулман, Томас Ф .; Цай, Джин-И (1986), «Проблема циклической раскраски и оценка разреженных гессианских матриц» (PDF) , SIAM Journal on Algebraic and Discrete Methods , 7 (2): 221–235, doi : 10.1137/0607026 , hdl : 1813/6485 .
• Фертен, Гийом; Распауд, Андре (2008), «Ациклическая раскраска графов максимальной пятой степени: достаточно девяти цветов», Information Processing Letters , 105 (2): 65–72, CiteSeerX   10.1.1.78.5369 , doi : 10.1016/j.ipl .2007.08.022 , S2CID   12886305 .
• Гебремедин, Ассефау Х.; Тарафдар, Ариджит; Потен, Алекс; Вальтер, Андреа (2008), «Эффективное вычисление разреженных гессианов с использованием раскраски и автоматического дифференцирования», Журнал INFORMS on Computing , 21 (2): 209–223, doi : 10.1287/ijoc.1080.0286 .
• Дженсен, Томми Р.; Тофт, Бьерн (1995), Проблемы раскраски графов , Нью-Йорк: Wiley-Interscience, ISBN  978-0-471-02865-9 .
• Косточка А. В. (1978), Верхние оценки хроматических функций графов , Докторская диссертация, Новосибирск. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
• Косточка Александр Владимирович; Стокер, Кристофер (2011), «Графики с максимальной степенью 5 ациклически раскрашиваются в 7 цветов» , Ars Mathematica Contemporanea , 4 (1): 153–164, doi : 10.26493/1855-3974.198.541 , MR   2785823 .
• Скулраттанакулчай, Сан (2004), «Ациклические раскраски субкубических графов», Information Processing Letters , 92 (4): 161–167, doi : 10.1016/j.ipl.2004.08.002 .
• Штейн, С.К. (1970), «B-множества и задачи раскраски», Бюллетень Американского математического общества , 76 (4): 805–806, doi : 10.1090/S0002-9904-1970-12559-9 .
• Штейн, С.К. (1971), «B-множества и плоские карты», Pacific Journal of Mathematics , 37 (1): 217–224, doi : 10.2140/pjm.1971.37.217 .
• Варагани, Сатиш; Венкая, В. Ч.; Ядав, Кишор; Котхапалли, Кишор (2009), «Ациклическая вершинная раскраска графов максимальной степени шесть», LAGOS'09 - Пятый латиноамериканский симпозиум по алгоритмам, графикам и оптимизации , Электронные заметки по дискретной математике, том. 35, Elsevier, стр. 177–182, doi : 10.1016/j.endm.2009.11.030 , MR   2579427

Внешние ссылки

• Раскраски звезд и ациклические раскраски (1973) , представленные на семинаре «Исследовательский опыт для аспирантов» (REGS) в Университете Иллинойса, 2008.
• Ациклическая раскраска графов максимальной степени ∆ , слайды доклада, представленные Г. Фертином и А. Распо на выставке EUROCOMB 05, Берлин, 2005 г.