Finite Playground

To verify is human; to prove, divine.

Graph coloring theorems revisited II – Vizing’s Theorem

Leave a comment

Alexandr Kostochka found the following new proof to the classical theorem.

Vizing’s Theorem.  For every simple graph G, \chi'(G) \le \Delta(G) + 1.

Proof.  We prove by contradiction; assume that G is a minimal counter-example (in terms of number of edges) to the statement; that is, G has no edge-(\Delta+1)-coloring.

Let \phi be an edge-(\Delta+1)-coloring of G-xy. For every v \in V(G), let O(v)=O_\phi(v) denote the set of colors in [\Delta+1] not used to color the edges incident to v; one can see that O(x) \cap O(y) = \emptyset.

Construct the auxiliary multidigraph H as follows: V(H) = N_G(y) and there is a directed edge from u to v in E(H) if \phi(vy) \in O(u). Intuitively an edge from u to v means that if we can recolor vy, then we can recolor uy as well. Let X be the set of vertices reachable in H from x (x \in X as well); any recoloring of an edge wy for w\in X will imply that we can color xy. Since the out-neighbors of a vertex reachable from x also are reachable from x, N^+_H(v) \subseteq X for every v \in X.  Therefore

\sum_{v \in X} d^+_{H[X]}(v) = |{E(H[X])}| = \sum_{v \in X} d^-_{H[X]}(v) \text,

and the theorem will be proven if we can show that

  1. d^+_{H[X]}(v) \ge \Delta - d(v) + 1 + [v = x] and
  2. d^-_{H[X]}(v) \le 1-[v=x] for all v \in X;

this implies

0 = \sum_{v \in X} \{d^+_{H[X]}(v) - d^-_{H[X]}(v)\} \ge 2 + \sum_{v \in X} (\Delta - d(v)) \ge 2,

a contradiction.  Items (1) and (2) follow from the following claims. Let \alpha \in O(y).

Claim 1 (Exchange argument).  \alpha\notin O(v) for every v\in X.
Proof sketch.  Recolor the edges of the form wy for each w on the path from x to v.

Claim 1 yields that for every v \in X and \beta \in O(v), there is some w \in N(y) with \phi(yw)=\beta. Then by the definition of H, vw\in H[X]. Because |{O(v)}| \ge \Delta+1-d(v) for each v\in V(G) and |{O(u)}| \ge \Delta+1-d_{G-xy}(u) = \Delta-d(u)+2 for u \in\{x,y\}; so

d^+_{H[X]}(v) \ge \Delta+1-d(v) for every v \in X and d^+_{H[X]}(x) \ge \Delta-d(x)+2.

Claim 2 (Distinct O-sets).  For all distinct v,w \in X, O(v) \cap O(w) = \emptyset.
Proof sketch.  A [\beta,\gamma]-path in G is a path whose edges are alternately colored with \beta and \gamma. A [\beta,\gamma](a,b)-path is a [\beta,\gamma]-path from a to b in G.

Claim: If v \in X and \beta \in O(v), then G contains an [\alpha,\beta](v,y)-path.  The claim follows from a Kempe-chain-like argument to recolor vy with \alpha.

Then suppose there are v,w\in X with \beta\in O(v)\cap O(w), then the [\beta,\alpha]-path starting at y must end at both v and w, a contradiction.

Claim 2 yields that d^-_{H[X]}(v) \le 1 for every v \in X and d^-_{H[X]}(x) = 0, because the color on edge vy corresponds to a unique in-neighbor of v (and there are no color on edge xy).

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s