Тотальное хроматическое число

Материал из WikiGrapp
Версия от 12:40, 20 сентября 2011; KEV (обсуждение | вклад) (Новая страница: «'''Тотальное хроматическое число''' (''Total chromatic number'') — наименьшее число цветов <math>\,\chi''(G)</…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Тотальное хроматическое число (Total chromatic number) — наименьшее число цветов [math]\displaystyle{ \,\chi''(G) }[/math], достаточное для раскраски вершин и ребер графа такой, что никакие смежные или инцидентные элементы графа не окрашены в один цвет. Ясно, что [math]\displaystyle{ \chi''(G) \geq \Delta + 1 }[/math], где [math]\displaystyle{ \,\Delta }[/math]степень графа. В 1997 г. было доказано, что планарный граф с [math]\displaystyle{ \Delta \geq 11 }[/math] имеет тотальное хроматическое число, равное [math]\displaystyle{ \,\Delta + 1 }[/math].

Литература

  • [J. Graph Theory]