Total coloring

Last updated July 05, 2023

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 χ″(G) of a graph G is the fewest colors needed in any total coloring of G.

The total graphT = 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; 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-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_{n,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, Vizing).

\chi ''(G)\leq \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 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 $\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 of the total graph of a graph G is at most Δ(G) + 2.

Related Research Articles

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.

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 of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

In graph theory, a uniquely colorable graph is a $k$ -chromatic graph that has only one possible (proper) $k$ -coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into $k$ independent sets and there is no way to partition them into $k - 1$ independent sets.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that

In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.

Vadim Georgievich Vizing was a Soviet and Ukrainian mathematician known for his contributions to graph theory, and especially for Vizing's theorem stating that the edges of any simple graph with maximum degree Δ can be colored with at most Δ + 1 colors.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.$

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by Vizing (1965), are a special type of triangle graphs, which are used in the field of edge coloring in particular.

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a branch of mathematics, the $k$ th power $G k$ of an undirected graph $G$ is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in $G$ is at most $k$ . Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: $G 2$ is called the square of $G$ , $G 3$ is called the cube of $G$ , etc.

<span class="mw-page-title-main">Adjacent-vertex-distinguishing-total coloring</span>

In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

References

Hind, Hugh; Molloy, Michael; Reed, Bruce (1998). "Total coloring with Δ + poly(log Δ) colors". SIAM Journal on Computing . 28 (3): 816–821. doi:10.1137/S0097539795294578.
Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
Kilakos, Kyriakos; Reed, Bruce (1993). "Fractionally colouring total graphs". Combinatorica. 13 (4): 435–440. doi:10.1007/BF01303515. S2CID 31163141.
Molloy, Michael; Reed, Bruce (1998). "A bound on the total chromatic number". Combinatorica. 18 (2): 241–280. doi:10.1007/PL00009820. hdl: 1807/9465 . S2CID 9600550.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.