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

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

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

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

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

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

Оценки на A (г) через Δ (г), максимальная степень из г, включая следующее:

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

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

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

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

это НП-полный чтобы определить, является ли A (г) ≤ 3. (Косточка 1978 )

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

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

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

Смотрите также

использованная литература

  • Бородин, О. В. (1979), "Об ациклических раскрасках плоских графов", Дискретная математика, 25 (3): 211–236, Дои:10.1016 / 0012-365X (79) 90077-3.
  • Бурштейн, М. И. (1979), "Каждый 4-валентный граф имеет ациклическую 5-раскраску", Soobšč. Акад. Наук Грузин. ССР, 93: 21–24.
  • Грюнбаум, Б. (1973), «Ациклические раскраски плоских графов», Israel J. Math., 14 (4): 390–408, Дои:10.1007 / BF02764716.
  • Коулман, Томас Ф .; Цай, Цзинь-И (1986), «Задача о циклической раскраске и оценка разреженных матриц Гессе» (PDF), Журнал SIAM по алгебраическим и дискретным методам, 7 (2): 221–235, Дои:10.1137/0607026.
  • Фертин, Гийом; Распо, Андре (2008), «Ациклическая раскраска графов максимальной степени пять: достаточно девяти цветов», Письма об обработке информации, 105 (2): 65–72, CiteSeerX  10.1.1.78.5369, Дои:10.1016 / j.ipl.2007.08.022.
  • Gebremedhin, Assefaw H .; Тарафдар, Ариджит; Потен, Алекс; Вальтер, Андреа (2008), «Эффективное вычисление разреженных гессианов с использованием раскраски и автоматического дифференцирования», ИНФОРМС Журнал по вычислительной технике, 21 (2): 209–223, Дои:10.1287 / ijoc.1080.0286.
  • Дженсен, Томми Р .; Тофт, Бьярн (1995), Проблемы с раскраской графиков, Нью-Йорк: Wiley-Interscience, ISBN  978-0-471-02865-9.
  • Косточка, А. В. (1978), Верхние границы хроматических функций графов, Докторская диссертация, Новосибирск.
  • Косточка, Александр В .; Стокер, Кристофер (2011), «Графики с максимальной степенью 5 ациклически 7-раскрашены», Ars Mathematica Contemporanea, 4 (1): 153–164, Дои:10.26493/1855-3974.198.541, Г-Н  2785823.
  • Скулраттанакулчай, Сан (2004), "Ациклические раскраски субкубических графов", Письма об обработке информации, 92 (4): 161–167, Дои:10.1016 / j.ipl.2004.08.002.
  • Штейн, С.К. (1970), «B-множества и проблемы раскраски», Бык. Амер. Математика. Soc., 76 (4): 805–806, Дои:10.1090 / S0002-9904-1970-12559-9.
  • Штейн, С.К. (1971), "B-множества и плоские отображения", Pacific J. Math., 37 (1): 217–224, Дои:10.2140 / pjm.1971.37.217.
  • Варагани, Сатиш; Venkaiah, V. Ch .; Ядав, Кишор; Котапалли, Кишор (2009), "Ациклическая раскраска вершин графов максимальной шестой степени", LAGOS'09 - Пятый латиноамериканский симпозиум по алгоритмам, графикам и оптимизации, Электронные заметки по дискретной математике, 35, Elsevier, стр. 177–182, Дои:10.1016 / j.endm.2009.11.030, Г-Н  2579427

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