Vizing's theorem

Theorem on graph edge coloring
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.

The theorem discovered by Russian 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).

When 1=Δ = 1, the graph G must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with 1=Δ(G) = 1 are of class one. When 1=Δ = 2, the graph G 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 1=Δ = 2 is of class one if and only if it is bipartite.

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 Δ in a graph G form an independent set, or more generally if the induced subgraph for this set of vertices is a forest, then G must be of class one. showed that almost all graphs are of class one. That is, in the Erdős–Rényi model of random graphs, in which all n vertex graphs are equally likely, let p(n) be the probability that an n vertex graph drawn from this distribution is of class one; then p(n) approaches one in the limit as n goes to infinity. For more precise bounds on the rate at which p(n) converges to one, see .

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

describe a polynomial time algorithm for coloring the edges of any graph with Δ + 1 colors, where Δ 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 uv is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest P (a graph in which each vertex has at most one outgoing edge) on the neighbors of u: for each neighbor p of u, the algorithm finds a color c that is not used by any of the edges incident to p, finds the vertex q (if it exists) for which edge uq has color c, and adds pq as an edge to P. There are two cases:
If the pseudoforest P constructed in this way contains a path from v to a vertex w that has no outgoing edges in P, then there is a color c that is available both at u and w. Recoloring edge uw with color c allows the remaining edge colors to be shifted one step along this path: for each vertex p in the path, edge up takes the color that was previously used by the successor of p in the path. This leads to a new coloring that includes edge uv. If, on the other hand, the path starting from v in the pseudoforest P leads to a cycle, let w be the neighbor of u at which the path joins the cycle, let c be the color of edge uw, and let d be a color that is not used by any of the edges at vertex u. Then swapping colors c and d 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 P and the recoloring steps of the algorithm can all be implemented in time O(n), where n is the number of vertices in the input graph. Since these steps need to be repeated m times, with each repetition increasing the number of colored edges by one, the total time is O(mn). In an unpublished technical report, claimed a faster time bound for the same problem of coloring with Δ + 1 colors.

In both and , Vizing mentions that his work was motivated by a theorem of showing that multigraphs could be colored with at most (3/2)Δ 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.