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.
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 Δ = 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 Δ(G) = 1 are of class one. When Δ = 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 Δ = 2 is of class one if and only if it is bipartite.
Proof This proof is inspired by Diestel (2000). Let G = (V, E) be a simple undirected graph. We proceed by induction on m, the number of edges. If the graph is empty, the theorem trivially holds. Let m > 0 and suppose a proper (Δ+1)-edge-coloring exists for all G − xy where xy ∈ E. We say that color α ∈ {1,...,Δ+1} is missing in x ∈ V with respect to proper (Δ+1)-edge-coloring c if c(xy) ≠ α for all y ∈ N(x). Also, let α/β-path from x denote the unique maximal path starting in x with α-colored edge and alternating the colors of edges (the second edge has color β, the third edge has color α and so on), its length can be 0. Note that if c is a proper (Δ+1)-edge-coloring of G then every vertex has a missing color with respect to c. Suppose that no proper (Δ+1)-edge-coloring of G exists. This is equivalent to this statement:
(1) Let xy ∈ E and c be arbitrary proper (Δ+1)-edge-coloring of G − xy and α be missing from x and β be missing from y with respect to c. Then the α/β-path from y ends in x. This is equivalent, because if (1) doesn't hold, then we can interchange the colors α and β on the α/β-path and set the color of xy to be α, thus creating a proper (Δ+1)-edge-coloring of G from c. The other way around, if a proper (Δ+1)-edge-coloring exists, then we can delete xy, restrict the coloring and (1) won't hold either. Now, let xy0 ∈ E and c0 be a proper (Δ+1)-edge-coloring of G − xy0 and α be missing in x with respect to c0. We define y0,...,yk to be a maximal sequence of neighbours of x such that c0(xyi) is missing in yi−1 with respect to c0 for all 0 < i ≤ k. We define colorings c1,...,ck as
ci(xyj)=c0(xyj+1) for all 0 ≤ j < i, ci(xyi) not defined, ci(e)=c0(e) otherwise. Then ci is a proper (Δ+1)-edge-coloring of G − xyi due to definition of y0,...,yk. Also, note that the missing colors in x are the same with respect to ci for all 0 ≤ i ≤ k. Let β be the color missing in yk with respect to c0, then β is also missing in yk with respect to ci for all 0 ≤ i ≤ k. Note that β cannot be missing in x, otherwise we could easily extend ck, therefore an edge with color β is incident to x for all cj. From the maximality of k, there exists 1 ≤ i < k such that c0(xyi) = β. From the definition of c1,...,ck this holds:
c0(xyi) = ci−1(xyi) = ck(xyi−1) = β Let P be the α/β-path from yk with respect to ck. From (1), P has to end in x. But α is missing in x, so it has to end with an edge of color β. Therefore, the last edge of P is yi−1x. Now, let P' be the α/β-path from yi−1 with respect to ci−1. Since P' is uniquely determined and the inner edges of P are not changed in c0,...,ck, the path P' uses the same edges as P in reverse order and visits yk. The edge leading to yk clearly has color α. But β is missing in yk, so P' ends in yk. 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 Δ 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. Erdős & Wilson (1977) 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 Frieze et al. (1988). The general classification problem of graphs into class one or class two was shown in 1981 to be NP-complete.
Planar graphs Vizing (1965) 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, Vizing (1965) states that all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible cases. Independently, Zhang (2000) and Sanders & Zhao (2001) 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 Appel & Haken (1976)) on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one.
… excerpt ends here. Continue reading the full article.
