# Finite Playground

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

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

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

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

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 會有問題), 證明完成.