L5 Coloring of Graph

符號定義

符號	意義
$\chi(G)$	著色數 (chromatic number)
$\chi'(G)$	邊著色數 (chromatic index)
$\omega(G)$	團數 (clique number)
$\alpha(G)$	最大獨立集大小
$G\vee H$	Join of graphs
$H$ -subdivision	對 $H$ 的邊反覆細分後所得圖

Vertex Coloring 點著色

圖 $G$ 的 $k$ -著色是一個映射 $f:V(G)\to S$ , 其中 $|S|=k$ 。

若對任意 $uv\in E(G)$ 都有 $f(u)\ne f(v)$ ，則稱為 proper $k$ -coloring。

若 $G$ 存在 proper $k$ -coloring ，則稱 $G$ 為 $k$ -colorable。

所有同色頂點形成一個 color class ，且每個 color class 都是 independent set。

Chromatic Number 著色數

圖 $G$ 的著色數記為 $\chi(G)$ ，表示完成 proper vertex coloring 所需的最少顏色數。

要證明 $\chi(G)=k$ ，通常要做兩件事:

找到 proper $k$ -coloring, 得到 $\chi(G)\le k$
證明不存在 proper $(k-1)$ -coloring, 得到 $\chi(G)\ge k$

常見圖:

$\chi(K_n)=n$
$\chi(P_n)=2$ for $n\ge2$
非平凡樹 $T$ : $\chi(T)=2$
$\chi(K_{m,n})=2$
$n$ 偶數時 $\chi(C_n)=2$
$n$ 奇數時 $\chi(C_n)=3$

二部圖與著色

對簡單連通圖 $G$ , 下列條件等價:

$\chi(G)=2$
$G$ 是 bipartite graph
$G$ 沒有 odd cycle

因此要證明一個圖不能 2-color，最常用的方法是找出 odd cycle。

Subgraph 與著色數

若 $H$ 是 $G$ 的子圖，則 $\chi(H)\le\chi(G)$ 。
因此若 $K_r\subseteq G$ , 則 $\chi(G)\ge r$ 。

Clique 與 Clique Number

Clique 是一組兩兩相鄰的頂點。

圖 $G$ 中最大的 clique 的頂點數稱為 clique number, 記為 $\omega(G)$ 。

因為 clique 中每個頂點都必須使用不同顏色: $\chi(G)\ge\omega(G)$

Independent Set

令 $\alpha(G)$ 為最大 independent set 的大小。

每個 color class 都是一個 independent set, 因此一種顏色最多只能包含 $\alpha(G)$ 個頂點。

所以: $\chi(G)\ge \left\lceil\frac{n(G)}{\alpha(G)}\right\rceil$

Join of Graphs

$G\vee H$ 表示保留兩圖原有邊，再將 $G$ 的每個頂點和 $H$ 的每個頂點全部相連。

因此兩圖不能共用顏色: $\chi(G\vee H)=\chi(G)+\chi(H)$

同時: $\omega(G\vee H)=\omega(G)+\omega(H)$

Coloring 方法

Greedy Coloring

Greedy Coloring 的做法:

先決定頂點順序
依序處理每個頂點
每次選擇尚未被已著色鄰居使用的最小顏色

Greedy 一定得到合法 coloring
不保證是 minimum coloring
頂點排序會影響最後使用的顏色數

Delta Plus One

對任意簡單圖 $G$ : $\chi(G)\le\Delta(G)+1$

每個頂點最多只有 $\Delta(G)$ 個鄰居，因此即使這些鄰居全使用不同顏色，準備 $\Delta(G)+1$ 色仍一定有一色可用。

只有 $K_n$ 與 $C_k$ (奇環) 可能達到上界

Welsh-Powell Theorem

令頂點 degree 依非遞增順序排列: $d_1\ge d_2\ge\cdots\ge d_n$

則: $\chi(G)\le 1+\max_i\min\{d_i,i-1\}$

第 $i$ 個頂點前面只有 $i-1$ 個頂點，且自己最多有 $d_i$ 個鄰居，所以前面最多有 $\min\{d_i,i-1\}$ 個相鄰頂點。

Brooks’s Theorem

若 $G$ 是簡單連通圖，且 $G$ 不是完全圖或奇環，則: $\chi(G)\le\Delta(G)$

一般上界是 $\chi(G)\le\Delta(G)+1$ , Brooks’s Theorem 將大部分 connected simple graph 改進成 $\Delta(G)$ 。

證明可分為四種情況 (講義 P39-50):

$\Delta(G)=2$
$\Delta(G)\ge3$ , 且不是 regular
$\Delta(G)\ge3$ , 是 regular 但不是 2-connected
$\Delta(G)\ge3$ , 是 regular 且 2-connected

Mycielski Construction

Mycielski construction 可構造出 clique 很小但 chromatic number 很大的圖。

設 $V(G)=\{v_1,\dots,v_n\}$ 。

新增:

$U=\{u_1,\dots,u_n\}$ : 若 $v_i$ 在原圖中與某頂點相鄰，則 $u_i$ 也與該頂點相鄰
一個新頂點 $w$ 與所有 $u_i$ 相鄰

若 $G$ 是 $K_3$ -free 且 $\chi(G)=k$ , 則經 Mycielski construction 得到的圖 $H$ :

仍是 $K_3$ -free
$\chi(H)=k+1$

證明在講義 P57-64

因此可以建構出 $\omega(G)=2$ , 但 $\chi(G)$ 任意大的圖。
這表示: $\chi(G)=k$ 並不代表 $G$ 一定含有 $K_k$ 子圖。