Vizing's theorem

Template:Short description 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 Template:Math of the graph. At least Template:Math colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Template:Math colors suffice, and "class two" graphs for which Template:Math colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Template:Math colors, where Template:Math is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

Discovery

The theorem discovered by Soviet mathematician Vadim G. Vizing was published in 1964 when Vizing was working in Novosibirsk and became known as Vizing's theorem. Indian mathematician R. P. Gupta independently discovered the theorem, while undertaking his doctorate (1965-1967).

Examples

When Template:Math, the graph Template:Mvar must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with Template:Math are of class one.

When Template:Math, the graph Template:Mvar must be a disjoint union of paths and cycles. If all cycles are even, they can be 2-edge-colored by alternating the two colors around each cycle. However, if there exists at least one odd cycle, then no 2-edge-coloring is possible. That is, a graph with Template:Math is of class one if and only if it is bipartite.

Proof

This proof is inspired by Template:Harvtxt.

Let Template:Math be a simple undirected graph. We proceed by induction on Template:Math, the number of edges. If the graph is empty, the theorem trivially holds. Let Template:Math and suppose a proper Template:Math-edge-coloring exists for all Template:Math where Template:Math.

We say that color Template:Math} is missing in Template:Math with respect to proper Template:Math-edge-coloring Template:Math if Template:Math for all Template:Math. Also, let Template:Math-path from Template:Math denote the unique maximal path starting in Template:Math with Template:Math-colored edge and alternating the colors of edges (the second edge has color Template:Math, the third edge has color Template:Math and so on), its length can be Template:Math. Note that if Template:Math is a proper Template:Math-edge-coloring of Template:Math then every vertex has a missing color with respect to Template:Math.

Suppose that no proper Template:Math-edge-coloring of Template:Math exists. This is equivalent to this statement:

(1) Let Template:Math and Template:Math be arbitrary proper Template:Math-edge-coloring of Template:Math and Template:Math be missing from Template:Math and Template:Math be missing from Template:Math with respect to Template:Math. Then the Template:Math-path from Template:Math ends in Template:Math.

This is equivalent, because if (1) doesn't hold, then we can interchange the colors Template:Math and Template:Math on the Template:Math-path and set the color of Template:Math to be Template:Math, thus creating a proper Template:Math-edge-coloring of Template:Math from Template:Math. The other way around, if a proper Template:Math-edge-coloring exists, then we can delete Template:Math, restrict the coloring and (1) won't hold either.

Now, let Template:Math and Template:Math be a proper Template:Math-edge-coloring of Template:Math and Template:Math be missing in Template:Math with respect to Template:Math. We define Template:Math to be a maximal sequence of neighbours of Template:Math such that Template:Math is missing in Template:Math with respect to Template:Math for all Template:Math.

We define colorings Template:Math as

Template:Math for all Template:Math,

Template:Math not defined,

Template:Math otherwise.

Then Template:Math is a proper Template:Math-edge-coloring of Template:Math due to definition of Template:Math. Also, note that the missing colors in Template:Math are the same with respect to Template:Math for all Template:Math.

Let Template:Math be the color missing in Template:Math with respect to Template:Math, then Template:Math is also missing in Template:Math with respect to Template:Math for all Template:Math. Note that Template:Math cannot be missing in Template:Math, otherwise we could easily extend Template:Math, therefore an edge with color Template:Math is incident to Template:Math for all Template:Math. From the maximality of Template:Math, there exists Template:Math such that Template:Math. From the definition of Template:Math this holds:

Template:Math

Let Template:Math be the Template:Math-path from Template:Math with respect to Template:Math. From (1), Template:Math has to end in Template:Math. But Template:Math is missing in Template:Math, so it has to end with an edge of color Template:Math. Therefore, the last edge of Template:Math is Template:Math. Now, let Template:Math be the Template:Math-path from Template:Math with respect to Template:Math. Since Template:Math is uniquely determined and the inner edges of Template:Math are not changed in Template:Math, the path Template:Math uses the same edges as Template:Math in reverse order and visits Template:Math. The edge leading to Template:Math clearly has color Template:Math. But Template:Math is missing in Template:Math, so Template:Math ends in Template:Math. Which is a contradiction with (1) above.

Classification of graphs

Several authors have provided additional conditions that classify some graphs as being of class one or class two, but do not provide a complete classification. For instance, if the vertices of the maximum degree Template:Math in a graph Template:Mvar form an independent set, or more generally if the induced subgraph for this set of vertices is a forest, then Template:Mvar must be of class one.

Template:Harvtxt showed that almost all graphs are of class one. That is, in the Erdős–Rényi model of random graphs, in which all Template:Mvar-vertex graphs are equally likely, let Template:Math be the probability that an Template:Mvar-vertex graph drawn from this distribution is of class one; then Template:Math approaches one in the limit as Template:Mvar goes to infinity. For more precise bounds on the rate at which Template:Math converges to one, see Template:Harvtxt.

Planar graphs

Template:Harvtxt showed that a planar graph is of class one if its maximum degree is at least eight. In contrast, he observed that for any maximum degree in the range from two to five, there exist planar graphs of class two. For degree two, any odd cycle is such a graph, and for degree three, four, and five, these graphs can be constructed from platonic solids by replacing a single edge by a path of two adjacent edges.

In Vizing's planar graph conjecture, Template:Harvtxt states that all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible cases. Independently, Template:Harvtxt and Template:Harvtxt partially proved Vizing's planar graph conjecture by showing that all planar graphs with maximum degree seven are of class one. Thus, the only case of the conjecture that remains unsolved is that of maximum degree six. This conjecture has implications for the total coloring conjecture.

The planar graphs of class two constructed by subdivision of the platonic solids are not regular: they have vertices of degree two as well as vertices of higher degree. The four color theorem (proved by Template:Harvtxt) on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one Template:Harv.

Graphs on nonplanar surfaces

In 1969, Branko Grünbaum conjectured that every 3-regular graph with a polyhedral embedding on any two-dimensional oriented manifold such as a torus must be of class one. In this context, a polyhedral embedding is a graph embedding such that every face of the embedding is topologically a disk and such that the dual graph of the embedding is simple, with no self-loops or multiple adjacencies. If true, this would be a generalization of the four color theorem, which was shown by Tait to be equivalent to the statement that 3-regular graphs with a polyhedral embedding on a sphere are of class one. However, Template:Harvtxt showed the conjecture to be false by finding snarks that have polyhedral embeddings on high-genus orientable surfaces. Based on this construction, he also showed that it is NP-complete to tell whether a polyhedrally embedded graph is of class one.

Algorithms

Template:Main Template:Harvtxt describe a polynomial time algorithm for coloring the edges of any graph with Template:Math colors, where Template:Math is the maximum degree of the graph. That is, the algorithm uses the optimal number of colors for graphs of class two, and uses at most one more color than necessary for all graphs. Their algorithm follows the same strategy as Vizing's original proof of his theorem: it starts with an uncolored graph, and then repeatedly finds a way of recoloring the graph in order to increase the number of colored edges by one.

More specifically, suppose that Template:Math is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest Template:Mvar (a graph in which each vertex has at most one outgoing edge) on the neighbors of Template:Mvar: for each neighbor Template:Mvar of Template:Mvar, the algorithm finds a color Template:Mvar that is not used by any of the edges incident to Template:Mvar, finds the vertex Template:Mvar (if it exists) for which edge Template:Mvar has color Template:Mvar, and adds Template:Mvar as an edge to Template:Mvar. There are two cases:

• If the pseudoforest Template:Mvar constructed in this way contains a path from Template:Mvar to a vertex Template:Mvar that has no outgoing edges in Template:Mvar, then there is a color Template:Mvar that is available both at Template:Mvar and Template:Mvar. Recoloring edge Template:Mvar with color Template:Mvar allows the remaining edge colors to be shifted one step along this path: for each vertex Template:Mvar in the path, edge Template:Mvar takes the color that was previously used by the successor of Template:Mvar in the path. This leads to a new coloring that includes edge Template:Mvar.
• If, on the other hand, the path starting from Template:Mvar in the pseudoforest Template:Mvar leads to a cycle, let Template:Mvar be the neighbor of Template:Mvar at which the path joins the cycle, let Template:Mvar be the color of edge Template:Mvar, and let Template:Mvar be a color that is not used by any of the edges at vertex Template:Mvar. Then swapping colors Template:Mvar and Template:Mvar on a Kempe chain either breaks the cycle or the edge on which the path joins the cycle, leading to the previous case.

With some simple data structures to keep track of the colors that are used and available at each vertex, the construction of Template:Mvar and the recoloring steps of the algorithm can all be implemented in time Template:Math, where Template:Mvar is the number of vertices in the input graph. Since these steps need to be repeated Template:Mvar times, with each repetition increasing the number of colored edges by one, the total time is Template:Math.

In an unpublished technical report, Template:Harvtxt claimed a faster $O(m\sqrt{n}\log n)$ time bound for the same problem of coloring with Template:Math colors.

History

In both Template:Harvtxt and Template:Harvtxt, Vizing mentions that his work was motivated by a theorem of Template:Harvtxt showing that multigraphs could be colored with at most Template:Math colors. Although Vizing's theorem is now standard material in many graph theory textbooks, Vizing had trouble publishing the result initially, and his paper on it appears in an obscure journal, Diskret. Analiz.

See also

• Brooks' theorem relating vertex colorings to maximum degree

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation. (In Russian.)
• Template:Citation.

External links

• Proof of Vizing's theorem at PlanetMath.