Total Coloring Conjecture

The total coloring conjecture, independently proposed by Behzad and Vizing, states that if is the maximum vertex degree of a finite simple graph , then its total chromatic number satisfies

Despite the similar name, this statement is distinct from the list total coloring conjecture, which was disproved by Noel (2026).

Explore with Wolfram|Alpha

More things to try:

alternating group A_5
eigenvectors {{1,0,0},{0,0,1},{0,1,0}}
limit (1+1/n)^n as n->infinity

References

Behzad, M. "Graphs and Their Chromatic Numbers." Doctoral thesis. East Lansing, MI: Michigan State University, 1965.Noel, J. A. "The List Total Colouring Conjecture Is False." 29 Sep 2026. https://arxiv.org/abs/2609.38417.Vizing, V. G. "Some Unsolved Problems in Graph Theory." Russian Math. Surveys 23, 125-141, 1968.

Cite this as:

Weisstein, Eric W. "Total Coloring Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TotalColoringConjecture.html

Total Coloring Conjecture

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications