# Total coloring

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Total_coloring
> Markdown URL: https://mediated.wiki/source/Total_coloring.md
> Source: https://en.wikipedia.org/wiki/Total_coloring
> Source revision: 1285190354
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Graph coloring of both the edges and vertices

Proper total coloring of [Foster cage](/source/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 problem in mathematics

**Conjecture:**

          χ
          ″

        (
        G
        )
        ≤
        Δ
        (
        G
        )
        +
        2.

    {\displaystyle \chi ''(G)\leq \Delta (G)+2.}

[More unsolved problems in mathematics](/source/List_of_unsolved_problems_in_mathematics)

In [graph theory](/source/Graph_theory), **total coloring** is a type of [graph coloring](/source/Graph_coloring) on the [vertices](/source/Vertex_(graph_theory)) and [edges](/source/Edge_(graph_theory)) 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** *χ*″(*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](/source/Graph_coloring) of *T*(*G*). A total coloring is a partitioning of the vertices and edges of the graph into [total independent sets](https://en.wikipedia.org/w/index.php?title=Total_independent_set&action=edit&redlink=1).

Some inequalities for *χ*″(*G*):

1. χ ″ ( G ) ≥ Δ ( G ) + 1. {\displaystyle \chi ''(G)\geq \Delta (G)+1.}

1. χ ″ ( G ) ≤ Δ ( G ) + 10 26 . {\displaystyle \chi ''(G)\leq \Delta (G)+10^{26}.} (Molloy, Reed 1998)

1. χ ″ ( G ) ≤ Δ ( G ) + 8 ln 8 ⁡ ( Δ ( G ) ) {\displaystyle \chi ''(G)\leq \Delta (G)+8\ln ^{8}(\Delta (G))} for sufficiently large Δ(*G*). (Hind, Molloy, Reed 1998)

1. χ ″ ( G ) ≤ ch ′ ⁡ ( G ) + 2. {\displaystyle \chi ''(G)\leq \operatorname {ch} '(G)+2.}

Here Δ(*G*) is the [maximum degree](/source/Glossary_of_graph_theory); and ch′(*G*), the [edge choosability](/source/List_edge-coloring).

Total coloring arises naturally since it is simply a mixture of vertex and edge colorings. The next step is to look for any [Brooks](/source/Brooks'_theorem)-typed or [Vizing](/source/Edge_coloring)-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 *χ*″(*G*) is Δ(*G*) + 1. Some graphs such as cycles of length n ≢ 0 mod 3 {\displaystyle n\not \equiv 0{\bmod {3}}} and complete bipartite graphs of the form Kn,n need Δ(*G*) + 2 colors but no graph has been found that requires more colors. This leads to the speculation that every graph needs either Δ(*G*) + 1 or Δ(*G*) + 2 colors, but never more:

- **Total coloring conjecture** ([Behzad](/source/Mehdi_Behzad), Vizing). χ ″ ( G ) ≤ Δ ( G ) + 2. {\displaystyle \chi ''(G)\leq \Delta (G)+2.}

Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by [Behzad](/source/Mehdi_Behzad) and [Vizing](/source/Vadim_G._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](/source/Bipartite_graph) and most [planar graphs](/source/Planar_graph) except those with maximum degree 6. The planar case can be completed if [Vizing's planar graph conjecture](/source/Edge_coloring) is true. Also, if the [list coloring conjecture](/source/List_edge-coloring) is true, then χ ″ ( G ) ≤ Δ ( G ) + 3. {\displaystyle \chi ''(G)\leq \Delta (G)+3.}

Results related to total coloring have been obtained. For example, Kilakos and Reed (1993) proved that the [fractional chromatic number](/source/Fractional_coloring) of the total graph of a graph G is at most Δ(*G*) + 2.

## References

- Hind, Hugh; Molloy, Michael; [Reed, Bruce](/source/Bruce_Reed_(mathematician)) (1998). "Total coloring with Δ + poly(log Δ) colors". *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*. **28** (3): 816–821. [doi](/source/Doi_(identifier)):[10.1137/S0097539795294578](https://doi.org/10.1137%2FS0097539795294578).

- Jensen, Tommy R.; Toft, Bjarne (1995). *Graph coloring problems*. New York: Wiley-Interscience. [ISBN](/source/ISBN_(identifier)) [0-471-02865-7](https://en.wikipedia.org/wiki/Special:BookSources/0-471-02865-7).

- Kilakos, Kyriakos; [Reed, Bruce](/source/Bruce_Reed_(mathematician)) (1993). "Fractionally colouring total graphs". *Combinatorica*. **13** (4): 435–440. [doi](/source/Doi_(identifier)):[10.1007/BF01303515](https://doi.org/10.1007%2FBF01303515). [S2CID](/source/S2CID_(identifier)) [31163141](https://api.semanticscholar.org/CorpusID:31163141).

- Molloy, Michael; [Reed, Bruce](/source/Bruce_Reed_(mathematician)) (1998). "A bound on the total chromatic number". *Combinatorica*. **18** (2): 241–280. [doi](/source/Doi_(identifier)):[10.1007/PL00009820](https://doi.org/10.1007%2FPL00009820). [hdl](/source/Hdl_(identifier)):[1807/9465](https://hdl.handle.net/1807%2F9465). [S2CID](/source/S2CID_(identifier)) [9600550](https://api.semanticscholar.org/CorpusID:9600550).

---
Adapted from the Wikipedia article [Total coloring](https://en.wikipedia.org/wiki/Total_coloring) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Total_coloring?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.