Total Coloring Conjecture
Canonical statement
View source LaTeX
A total coloring of a finite simple graph \(G\) assigns
colors to \(V(G)\cup E(G)\) so that adjacent vertices, adjacent edges, and
every incident vertex--edge pair receive different colors. If
\(\chi''(G)\) is the least number of colors in such a coloring, then
\[
\chi''(G)\leq\Delta(G)+2.
\]
Here \(\Delta(G)\) is the maximum vertex degree of \(G\).Notes
The total chromatic number of a finite simple graph is the least number of colors needed to color all vertices and edges so that adjacent vertices, adjacent edges, and every incident vertex–edge pair receive different colors. A vertex of maximum degree together with its incident edges already gives mutually conflicting elements, so always. The Total Coloring Conjecture, proposed in the mid-1960s independently by Behzad [Behzad1965Total] and Vizing [Vizing1968Total], asserts that for every finite simple graph.
The conjecture has been verified for many classes of graphs, and the known general upper bounds come remarkably close: Molloy and Reed proved that for graphs of sufficiently large maximum degree the total chromatic number is at most plus an absolute constant [MolloyReed1998Total], and other bounds are asymptotically close to .
The gap between such bounds and the sharp has never been closed in general, and the conjecture remains open.
References (3)
- [Behzad1965Total]
Graphs and Their Chromatic Numbers
Mehdi Behzad · 1965 · misc
- [Vizing1968Total]
Some unsolved problems in graph theory
Open ↗V. G. Vizing · 1968 · misc
- [MolloyReed1998Total]
A bound on the total chromatic number
Open ↗Michael Molloy and Bruce Reed · 1998 · misc
The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.