Раскраска звезды

Звездное хроматическое число на графике Дика равно 4, а хроматическое число - 2.

В теории графов математике , А звезда раскраска графа G является (собственно) вершина окраски , в которой каждый путь на четырех вершин использует по крайней мере , три различных цвета. Точно так же в звездной раскраске индуцированные подграфы, образованные вершинами любых двух цветов, имеют компоненты связности, которые являются звездными графами . Раскраска звезд была введена Грюнбаумом (1973) . Звезда хроматического числа из G является наименьшее количество цветов , необходимых для звезды цвета G .${\ Displaystyle \ чи _ {s} (G)}$

Одним из обобщений звездной раскраски является тесно связанная концепция ациклической раскраски , где требуется, чтобы каждый цикл использовал по крайней мере три цвета, поэтому двухцветные индуцированные подграфы являются лесами . Если мы обозначим ациклическое хроматическое число графа G через , мы получим это , и фактически каждая звездная раскраска графа G является ациклической раскраской.${\ Displaystyle \ чи _ {а} (G)}$${\ Displaystyle \ чи _ {а} (G) \ leq \ чи _ {s} (G)}$

Нешетржил и Оссона де Мендез (2003) доказали, что звездное хроматическое число ограничено на каждом собственном минорном закрытом классе . Эти результаты были далее обобщены Nešetřil & Ossona de Mendez (2006) на все раскраски с малой глубиной дерева (стандартная раскраска и раскраска звезд - это раскраски с низкой глубиной дерева с соответствующими параметрами 1 и 2).

Сложность

Это было продемонстрировано Albertson et al. (2004), что NP-полный, чтобы определить , является ли граф , даже если G , является и плоским, и двудольным графом .Коулман и Море (1984) показали, что найти оптимальную раскраску звезд NP-сложно, даже если G - двудольный граф.${\ Displaystyle \ чи _ {s} (G) \ Leq 3}$

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

• Альбертсон, Майкл О .; Chappell, Glenn G .; Кирстед, Хэл А .; Кюндген, Андре; Рамамурти, Радхика (2004), « Раскрашивание без двухцветных P ₄ » , Электронный журнал комбинаторики , 11 (1), MR  2056078.
• Коулман, Томас Ф .; Более того , Джордж (1984), "Оценка разреженного Гессиан матрицы и проблемы раскраски графа" (PDF) , Математическое программирование , 28 (3): 243-270, DOI : 10.1007 / BF02612334 , ЛВП : 1813/6374 , МР  0736293.
• Фертин, Гийом; Распо, Андре; Рид, Брюс (2004), "Звезда раскраски графов" , Журнал теории графов , 47 (3): 163-182, DOI : 10.1002 / jgt.20029 , MR  2089462.
• Грюнбаум, Бранко (1973), "ациклические раскраски плоских графов", Израиль Журнал математики , 14 : 390-408, DOI : 10.1007 / BF02764716 , MR  0317982.
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2003), «Раскраски и гомоморфизмы второстепенных замкнутых классов», Дискретная и вычислительная геометрия: Festschrift Гудмана-Поллака , алгоритмы и комбинаторика, 25 , Springer-Verlag, стр. 651–664, MR  2038495.
• Нешетржил, Ярослав ; Ossona де Мендес, Патрис (2006), "глубина дерева, подграф раскраска и гомоморфизм оценка", Европейский журнал комбинаторика , 27 (6): 1022-1041, DOI : 10.1016 / j.ejc.2005.01.010 , MR  2226435.

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

• Раскраски звезд и ациклические раскраски (1973) , представленные на Исследовательском опыте для аспирантов (REGS) в Университете Иллинойса, 2008.