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

В теории графов ациклическая раскраска — это (правильная) раскраска вершин , в которой каждый 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, если Δ( G ) = 5. (Косточка и Стокер, 2011)
A( G ) ≤ 12, если Δ( G ) = 6. (Варагани и др., 2009)

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

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

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

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

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

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

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

Алгоритм линейного времени для ациклической раскраски графа максимальной степени ≤ 3 с использованием 4 цветов или меньше был предложен Скулраттанакулчаем (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 Journal 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 .
Varagani, Satish; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009), "Ациклическая раскраска вершин графов максимальной степени шесть", LAGOS'09 – Пятый латиноамериканский симпозиум по алгоритмам, графам и оптимизации , Электронные заметки по дискретной математике, т. 35, Elsevier, стр. 177–182, doi :10.1016/j.endm.2009.11.030, MR 2579427

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

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