TOPICS
Search

Total Chromatic Number

The total chromatic number of a graph G is the chromatic number of its total graph T(G) (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 G so that adjacent vertices, adjacent edges, and incident vertex-edge pairs all receive distinct colors. The total chromatic number is commonly denoted chi^('')(G).

If Delta(G) is the maximum vertex degree of a simple graph G, then

chi^('')(G)>=Delta(G)+1.

The total coloring conjecture, independently proposed by Behzad and Vizing, asserts that

chi^('')(G)<=Delta(G)+2

for every finite simple graph G (Behzad 1965, Vizing 1968).

See also

Chromatic Number, Edge Chromatic Number, Total Coloring Conjecture, Total Graph, Vertex Coloring

Explore with Wolfram|Alpha

References

Behzad, M. Graphs and Their Chromatic Numbers. Doctoral thesis, Michigan State University, East Lansing, MI, 1965.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.Vizing, V. G. "Some Unsolved Problems in Graph Theory." Russian Math. Surveys 23, 125-141, 1968.

Cite this as:

Weisstein, Eric W. "Total Chromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TotalChromaticNumber.html

Subject classifications