Finite Playground

To verify is human; to prove, divine.

Leave a comment

Graph coloring theorems revisited II – Vizing’s Theorem

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

Leave a comment

Graph coloring theorems revisited I – Brook’s Theorem and Rubin’s Block Theorem

這學期在修學校著名的組合數學課程, 課本當然是使用 Douglas B. West 的新書草稿.  其中有許多內容是全新的, 我想這會成為新一代的組合學以及圖論教科書吧?

今天要談的是圖著色中著名的定理之一 — Brooks’ Theorem, 說明只要不是完全圖或奇圈 (odd cycle), 我們便可以稍稍改進單純的上界 \Delta(G) +1\Delta.  但當初學到的證明簡直是魔術, 看不出什麼東西.  在 West 的新書中使用了 [Entringer85] 的結果, 說明為何這兩種圖比較特別.

Rubin’s Block Theorem.  令 G 為一雙連通圖; 若 G 不是完全圖或奇圈, 則 G 中有一個含有最多一條弦 (chord) 的偶圈.

很奇怪的圖結構定理, 但我們來看看要怎麼使用它!  定義圖 G 為 degree-choosable 如果對於任意的色組函數將每個圖中的點對應到一組可選擇的顏色, 且每個點上的顏色至少跟點的 degree 相同, 我們都保證可以從每組顏色中選取一種將圖適當的著色.  底下這兩個 Lemma 不難證:

Lemma 1.  給定連通圖 G 與一色組函數 L, (i) 若有某個點 v 的顏色選擇多於 degree, 則圖 G 可順利著色; (ii) 若圖 G 為雙連通, 且有兩個點上的顏色組不同, 則圖 G 可順利著色.

Lemma 2.  連通圖 G 若存在一 degree-choosable 生成子圖 H, 則圖 G 也是 degree-choosable.
Proof.  By Lemma 1(a).

利用 Lemma 1,2 與 Rubin’s Block Theorem 我們可以證明底下的若且唯若條件, 不過我們只需要唯若方向就是; 所以暫時先證一邊!

Theorem.  圖 G 不為 degree-choosable 若且唯若每個雙連通集 (block) 皆為完全圖或奇圈.
Proof.  由 Lemma 2 與 Block Theorem 我們只需要證明含有最多一條弦的偶圈是 degree-choosable; 但利用 Lemma 1(b) 這很明顯.

Brooks’ Theorem (extended).  若圖 G 不是完全圖或奇圈, 則 \chi_{\ell}(G) \le \Delta(G).
Proof.  利用上面的 Theorem 我們只需要處理當所有雙連通集都是完全圖或奇圈的情形.  如果有個點的 degree 比 \Delta(G) 小, 利用 Lemma 1(a) 就結束了; 所以 G 一定是 \Delta(G)-正則 (regular); 但在這種情況下表示我們只有一個 block (不然斷點的 degree 會有問題), 證明完成.

不過, 這其實不是我最喜歡的證明; degree-choosable 的部分可以被另一個定理取代, 並且能更增強證明的結果; 我們留到下次再介紹 Alon-Tarsi Theorem.