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

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

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

Верхняя граница [ править ]

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

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

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

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

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

Алгоритмы и сложность [ править ]

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

Coleman & Cai (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.
  • Grünbaum, B. (1973), "Ациклические раскраски плоских графов", Israel J. Math. , 14 (4): 390-408, DOI : 10.1007 / BF02764716 .
  • Коулман, Томас Ф .; Cai, Jin-Yi (1986), "Циклическая раскраска Проблема и оценка разреженных матриц Гессе" (PDF) , SIAM журнал на алгебраических и дискретных методов , 7 (2): 221-235, дои : 10,1137 / 0607026.
  • Фертин, Гийом; Распо, Андре (2008), «Ациклическая раскраска графов максимальной степени пять: достаточно девяти цветов», Письма об обработке информации , 105 (2): 65–72, CiteSeerX  10.1.1.78.5369 , doi : 10.1016 / j.ipl .2007.08.022.
  • Gebremedhin, Assefaw H .; Тарафдар, Ариджит; Потен, Алекс; Вальтер, Андреа (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), Верхние оценки хроматических функций графов , Дис. ... докт. Дис., Новосибирск..
  • Косточка, Александр В .; Стокер, Кристофер (2011), "Графы с максимальной степенью 5 являются ациклический 7-раскраской" , Арс Mathematica Contemporanea , 4 (1) 153-164, DOI : 10,26493 / 1855-3974.198.541 , МР  2785823.
  • Skulrattanakulchai, Сан (2004), "ациклические раскраски subcubic графов", Information Processing Letters , 92 (4): 161-167, DOI : 10.1016 / j.ipl.2004.08.002.
  • Stein, SK (1970), "B-множества и проблемы раскраски", Bull. Амер. Математика. Soc. , 76 (4): 805–806, DOI : 10.1090 / S0002-9904-1970-12559-9 .
  • Stein, SK (1971), "B-множества и плоские отображения", Pacific J. Math. , 37 (1): 217-224, DOI : 10,2140 / pjm.1971.37.217 .
  • Варагани, Сатиш; Venkaiah, V. Ch .; Ядав, Кишор; Котапалли, Кишор (2009), «Ациклическая вершинная раскраска графов максимальной шестой степени», LAGOS'09 - Пятый латиноамериканский симпозиум по алгоритмам, графикам и оптимизации , Электронные заметки по дискретной математике, 35 , Elsevier, стр. 177–182, DOI : 10.1016 / j.endm.2009.11.030 , МР  2579427

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

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