The total chromatic number of a graph 
is the chromatic number
of its total graph 
(Harary and Palmer 1973, p. 269). Equivalently, it
is the smallest number of colors needed to color both the graph
vertices and graph edges of 
so that adjacent vertices, adjacent edges, and incident vertex-edge
pairs all receive distinct colors. The total chromatic number is commonly denoted
.
If 
is the maximum vertex degree of a simple
graph 
,
then
 |
The total coloring conjecture, independently proposed by Behzad and Vizing, asserts that
 |
for every finite simple graph 
(Behzad 1965, Vizing 1968).
For a restricted class of planar graphs, Zhu (2026) proved that every maximal planar graph 
with maximum
vertex degree 
satisfies 
.
The corresponding bound for all planar graphs of
maximum vertex degree 6 remains open. Completing
a planar graph to a maximal
planar graph can increase its maximum vertex
degree, so the maximal case does not settle the general case.
Zhu (2026) also proved a coloring-extension theorem with no planarity assumption. Every proper vertex coloring of a graph with maximum vertex degree at most 3 using colors from a fixed set of four colors extends to a total coloring using those four colors and one additional color.
