graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, total coloring is a type of

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

on the vertices and

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed b ...

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 χ″(''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''). A total coloring is a partitioning of the vertices and edges of the graph into total independent sets. Some inequalities for χ″(''G''): # χ″(''G'') ≥ Δ(''G'') + 1. # χ″(''G'') ≤ Δ(''G'') + 10²⁶. (Molloy, Reed 1998) # χ″(''G'') ≤ Δ(''G'') + 8 ln⁸(Δ(''G'')) for sufficiently large Δ(''G''). (Hind, Molloy, Reed 1998) # χ″(''G'') ≤ ch′(''G'') + 2. Here Δ(''G'') is the

maximum degree This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

; and ch′(''G''), 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 Brooks may refer to: Places ;Antarctica *Cape Brooks ;Canada *Brooks, Alberta ;United States * Brooks, Alabama *Brooks, Arkansas * Brooks, California * Brooks, Georgia *Brooks, Iowa *Brooks, Kentucky *Brooks, Maine *Brooks Township, Michigan * ...

-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 χ″(''G'') is Δ(''G'') + 1. Some graphs such as cycles of length

n \not \equiv 0 \bmod 3

and complete bipartite graphs of the form

K_

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 Behzad ( fa, بهزاد, link=no) may refer to: Places in Iran *Bagh-e Behzad, a village in Javanmardi Rural District, Khanmirza District, Lordegan County, Chaharmahal and Bakhtiari Province *Behzad Kola, a village in Qareh Toghan Rural District, ...

, Vizing).

\chi''(G) \le \Delta(G)+2.

Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by

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 graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

s and most

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s 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

\chi''(G) \le \Delta(G) +3.

Results related to total coloring have been obtained. For example, Kilakos and Reed (1993) proved that the

fractional chromatic number Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent ve ...

of the total graph of a graph ''G'' is at most Δ(''G'') + 2.

References

* *Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. . * *{{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 , hdl-access = free Graph coloring