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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

  • [J. Graph Theory]