Total coloring

When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color.

The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G. The total graph T = T(G) of a graph G is a graph such that (i) the vertex set of T corresponds to the vertices and edges of G and (ii) two vertices are adjacent in T if and only if their corresponding elements are either adjacent or incident in G. Then total coloring of G becomes a (proper) vertex coloring of T(G).

Some inequalities for χ″(G): Here Δ(G) is the maximum degree; and ch′(G), the edge choosability.

The next step is to look for any Brooks-typed or Vizing-typed upper bound on the total chromatic number in terms of maximum degree.

The total coloring version of maximum degree upper bound is a difficult problem that has eluded mathematicians for 50 years.