{{short description|Graph coloring of both the edges and vertices}} [[Image:Total coloring foster cage.svg|right|300px|thumb|Proper total coloring of [[Foster cage]] with 6 colors. The '''total chromatic number''' of this graph is 6 since the degree of each vertex is 5 (5 adjacent edges + 1 vertex = 6).]] {{unsolved|mathematics|'''Conjecture:''' <math>\chi''(G) \le \Delta(G)+2.</math>}}
In [[graph theory]], '''total coloring''' is a type of [[graph coloring]] on the [[vertex (graph theory)|vertices]] and [[edge (graph theory)|edge]]s 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''' {{math|''χ''″(''G'')}} of a graph {{mvar|G}} is the fewest colors needed in any total coloring of {{mvar|G}}.
The '''total graph''' {{math|1=''T'' = ''T''(''G'')}} of a graph {{mvar|G}} is a graph such that (i) the vertex set of {{mvar|T}} corresponds to the vertices and edges of {{mvar|G}} and (ii) two vertices are adjacent in {{mvar|T}} if and only if their corresponding elements are either adjacent or incident in {{mvar|G}}. Then total coloring of {{mvar|G}} becomes a [[Graph coloring|(proper) vertex coloring]] of {{math|''T''(''G'')}}. A total coloring is a partitioning of the vertices and edges of the graph into [[total independent set]]s.
Some inequalities for {{math|''χ''″(''G'')}}: # <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 {{math|Δ(''G'')}}. (Hind, Molloy, Reed 1998) # <math>\chi''(G) \leq \operatorname{ch}'(G) + 2.</math> Here {{math|Δ(''G'')}} is the [[Glossary of graph theory|maximum degree]]; and {{math|ch′(''G'')}}, the [[List edge-coloring|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' theorem|Brooks]]-typed or [[Edge coloring|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 {{math|''χ''″(''G'')}} is {{math|Δ(''G'') + 1}}. Some graphs such as cycles of length <math>n \not \equiv 0 \bmod 3</math> and complete bipartite graphs of the form {{mvar|K{{sub|n,n}}}} need {{math|Δ(''G'') + 2}} colors but no graph has been found that requires more colors. This leads to the speculation that every graph needs either {{math|Δ(''G'') + 1}} or {{math|Δ(''G'') + 2}} colors, but never more:
:'''Total coloring conjecture''' ([[Mehdi Behzad|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 [[Mehdi Behzad|Behzad]] and [[Vadim G. Vizing|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 graph]]s and most [[planar graph]]s except those with maximum degree 6. The planar case can be completed if [[Edge coloring|Vizing's planar graph conjecture]] is true. Also, if the [[List edge-coloring|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 coloring|fractional chromatic number]] of the total graph of a graph {{mvar|G}} is at most {{math|Δ(''G'') + 2}}.
== References == *{{cite journal|doi = 10.1137/S0097539795294578 | last1 = Hind | first1 = Hugh | last2 = Molloy | first2 = Michael | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician) | year = 1998 | title = Total coloring with Δ + poly(log Δ) colors | journal = [[SIAM Journal on Computing]] | volume = 28 | issue = 3| pages = 816–821 }} *Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. {{isbn|0-471-02865-7}}. *{{cite journal|last1 = Kilakos | first1 = Kyriakos | last2 = Reed | first2 = Bruce | author2-link = Bruce Reed (mathematician) | year = 1993 | title = Fractionally colouring total graphs | journal = Combinatorica | volume = 13 | issue = 4| pages = 435–440 | doi = 10.1007/BF01303515 | s2cid = 31163141 }} *{{cite journal|last1 = Molloy | first1 = Michael | last2 = Reed | first2 = Bruce | author2-link = Bruce Reed (mathematician) | year = 1998 | title = A bound on the total chromatic number | journal = Combinatorica | volume = 18 | issue = 2| pages = 241–280 | doi = 10.1007/PL00009820 | hdl = 1807/9465 | s2cid = 9600550 | hdl-access = free }}
[[Category:Graph coloring]]