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 conne ...

, 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 o ...

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 by ...

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 set Total may refer to: Mathematics * Total, the summation of a set of numbers * Total order, a partial order without incomparable pairs * Total relation, which may also mean ** connected relation (a binary relation in which any two elements are compa ...

s. 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; 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, Vizing).

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

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 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 are ...

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 cross ...

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 In mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring ...

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 v ...

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