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

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

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

Литература

  • [J. Graph Theory]