In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. 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 Template:Math of a graph Template:Mvar is the fewest colors needed in any total coloring of Template:Mvar.
The total graph Template:Math of a graph Template:Mvar is a graph such that (i) the vertex set of Template:Mvar corresponds to the vertices and edges of Template:Mvar and (ii) two vertices are adjacent in Template:Mvar if and only if their corresponding elements are either adjacent or incident in Template:Mvar. Then total coloring of Template:Mvar becomes a (proper) vertex coloring of Template:Math. A total coloring is a partitioning of the vertices and edges of the graph into total independent sets.
Some inequalities for Template:Math:
- <math>\chi(G) \geq \Delta(G) + 1.</math>
- <math>\chi(G) \leq \Delta(G) + 10^{26}.</math> (Molloy, Reed 1998)
- <math>\chi(G) \leq \Delta(G) + 8 \ln^8(\Delta(G))</math> for sufficiently large Template:Math. (Hind, Molloy, Reed 1998)
- <math>\chi(G) \leq \operatorname{ch}'(G) + 2.</math>
Here Template:Math is the maximum degree; and Template:Math, the edge choosability.
Total coloring arises naturally since it is simply a mixture of vertex and edge colorings. 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. A trivial lower bound for Template:Math is Template:Math. Some graphs such as cycles of length <math>n \not \equiv 0 \bmod 3</math> and complete bipartite graphs of the form Template:Mvar need Template:Math colors but no graph has been found that requires more colors. This leads to the speculation that every graph needs either Template:Math or Template:Math colors, but never more:
- Total coloring conjecture (Behzad, Vizing). <math>\chi(G) \le \Delta(G)+2.</math>
Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by Behzad and Vizing in numerous occasions between 1964 and 1968 (see Jensen & Toft). The conjecture is known to hold for a few important classes of graphs, such as all bipartite graphs and most planar graphs except those with maximum degree 6. The planar case can be completed if Vizing's planar graph conjecture is true. Also, if the list coloring conjecture is true, then <math>\chi(G) \le \Delta(G) +3.</math>
Results related to total coloring have been obtained. For example, Kilakos and Reed (1993) proved that the fractional chromatic number of the total graph of a graph Template:Mvar is at most Template:Math.
ReferencesEdit
- Template:Cite journal
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. Template:Isbn.
- Template:Cite journal
- Template:Cite journal