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

Тотальное хроматическое число (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]