Vizing's theorem

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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. Vizing's theorem_sentence_0

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. Vizing's theorem_sentence_1

A more generalized 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. Vizing's theorem_sentence_2

The theorem is named for Vadim G. Vizing who published it in 1964. Vizing's theorem_sentence_3

Examples Vizing's theorem_section_0

When Δ = 1, the graph G must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. Vizing's theorem_sentence_4

That is, all graphs with Δ(G) = 1 are of class one. Vizing's theorem_sentence_5

When Δ = 2, the graph G must be a disjoint union of paths and cycles. Vizing's theorem_sentence_6

If all cycles are even, they can be 2-edge-colored by alternating the two colors around each cycle. Vizing's theorem_sentence_7

However, if there exists at least one odd cycle, then no 2-edge-coloring is possible. Vizing's theorem_sentence_8

That is, a graph with Δ = 2 is of class one if and only if it is bipartite. Vizing's theorem_sentence_9

Proof Vizing's theorem_section_1

This proof is inspired by . Vizing's theorem_sentence_10

Let G = (V, E) be a simple undirected graph. Vizing's theorem_sentence_11

We proceed by induction on m, the number of edges. Vizing's theorem_sentence_12

If the graph is empty, the theorem trivially holds. Vizing's theorem_sentence_13

Let m > 0 and suppose a proper (Δ+1)-edge-coloring exists for all G − xy where xy ∈ E. Vizing's theorem_sentence_14

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). Vizing's theorem_sentence_15

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. Vizing's theorem_sentence_16

Note that if c is a proper (Δ+1)-edge-coloring of G then every vertex has a missing color with respect to c. Vizing's theorem_sentence_17

Suppose that no proper (Δ+1)-edge-coloring of G exists. Vizing's theorem_sentence_18

This is equivalent to this statement: Vizing's theorem_sentence_19

Vizing's theorem_description_list_0

  • (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.Vizing's theorem_item_0_0

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 an edge, restrict the coloring and (1) won't hold either. Vizing's theorem_sentence_20

Now, let xy0 ∈ E and c0 be a proper (Δ+1)-edge-coloring of G − xy0 and α be missing in x with respect to c0. Vizing's theorem_sentence_21

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. Vizing's theorem_sentence_22

We define coloring c1,...,ck as Vizing's theorem_sentence_23

Vizing's theorem_description_list_1

  • ci(xyj)=c0(xyj+1) for all 0 ≤ j < i,Vizing's theorem_item_1_1
  • ci(xyi) not defined,Vizing's theorem_item_1_2
  • ci(e)=c0(e) otherwise.Vizing's theorem_item_1_3

Then ci is a proper (Δ+1)-edge-coloring of G − xyi due to definition of y0,...,yk. Vizing's theorem_sentence_24

Also, note that the missing colors in x are the same with respect to ci for all 0 ≤ i ≤ k. Vizing's theorem_sentence_25

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. Vizing's theorem_sentence_26

From the maximality of k, there exists 1 ≤ i < k such that c0(xyi) = β. Vizing's theorem_sentence_27

From the definition of c1,...,ck this holds: Vizing's theorem_sentence_28

Vizing's theorem_description_list_2

  • c0(xyi) = ci−1(xyi) = ck(xyi−1) = βVizing's theorem_item_2_4

Let P be the α/β-path from yk with respect to ck. Vizing's theorem_sentence_29

From (1), P has to end in x. Vizing's theorem_sentence_30

But α is missing in x, so it has to end with an edge of color β. Vizing's theorem_sentence_31

Therefore, the last edge of P is yi−1x. Vizing's theorem_sentence_32

Now, let P' be the α/β-path from yi−1 with respect to ci−1. Vizing's theorem_sentence_33

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. Vizing's theorem_sentence_34

The edge leading to yk clearly has color α. Vizing's theorem_sentence_35

But β is missing in yk, so P' ends in yk. Vizing's theorem_sentence_36

Which is a contradiction with (1) above. Vizing's theorem_sentence_37

Classification of graphs Vizing's theorem_section_2

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. Vizing's theorem_sentence_38

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. Vizing's theorem_sentence_39

showed that almost all graphs are of class one. Vizing's theorem_sentence_40

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. Vizing's theorem_sentence_41

For more precise bounds on the rate at which p(n) converges to one, see . Vizing's theorem_sentence_42

Planar graphs Vizing's theorem_section_3

showed that a planar graph is of class one if its maximum degree is at least eight. Vizing's theorem_sentence_43

In contrast, he observed that for any maximum degree in the range from two to five, there exist planar graphs of class two. Vizing's theorem_sentence_44

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. Vizing's theorem_sentence_45

In Vizing's planar graph conjecture, states that all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible cases. Vizing's theorem_sentence_46

partially proved Vizing's planar graph conjecture by showing that all planar graphs with maximum degree seven are of class one. Vizing's theorem_sentence_47

Thus, the only case of the conjecture that remains unsolved is that of maximum degree six. Vizing's theorem_sentence_48

This conjecture has implications for the total coloring conjecture. Vizing's theorem_sentence_49

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. Vizing's theorem_sentence_50

The four color theorem (proved by ) on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one (). Vizing's theorem_sentence_51

Graphs on nonplanar surfaces Vizing's theorem_section_4

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. Vizing's theorem_sentence_52

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. Vizing's theorem_sentence_53

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. Vizing's theorem_sentence_54

However, showed the conjecture to be false by finding snarks that have polyhedral embeddings on high-genus orientable surfaces. Vizing's theorem_sentence_55

Based on this construction, he also showed that it is NP-complete to tell whether a polyhedrally embedded graph is of class one. Vizing's theorem_sentence_56

Algorithms Vizing's theorem_section_5

describe a polynomial time algorithm for coloring the edges of any graph with Δ + 1 colors, where Δ is the maximum degree of the graph. Vizing's theorem_sentence_57

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. Vizing's theorem_sentence_58

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. Vizing's theorem_sentence_59

More specifically, suppose that uv is an uncolored edge in a partially colored graph. Vizing's theorem_sentence_60

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: Vizing's theorem_sentence_61

Vizing's theorem_unordered_list_3

  • 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.Vizing's theorem_item_3_5
  • 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.Vizing's theorem_item_3_6

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. Vizing's theorem_sentence_62

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). Vizing's theorem_sentence_63

History Vizing's theorem_section_6

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. Vizing's theorem_sentence_64

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. Vizing's theorem_sentence_65

Analiz. Vizing's theorem_sentence_66

See also Vizing's theorem_section_7

Vizing's theorem_unordered_list_4

  • Brooks' theorem relating vertex colorings to maximum degreeVizing's theorem_item_4_7

Credits to the contents of this page go to the authors of the corresponding Wikipedia page:'s theorem.