色臨界圖

數學分支圖論中，色臨界圖或臨界圖（英語：critical graph）是圖染色問題中一類特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。這一類圖具有一些非常好的性質，能在很多證明定理中發揮用處。

定義

如果圖$G$的任意一個真子圖$G'\subset G$，其色數均滿足$\chi (G')<\chi (G)$，則稱$G$為$\chi (G)$色臨界圖（英語：$\chi (G)$-critical graph）。

相關定義

圖染色數

參見：圖染色問題

對於給定的圖$G$，存在$k$種顏色和一種染色方案，將圖中$G$每一個頂點都染成$k$種顏色中的一種。如果染色方案滿足一下條件，那麼將稱該染色方案為恰當的染色方案：對於圖$G$中任意兩個頂點$u,v$，如果$uv\in E(G)$，那麼$u,v$所染成的顏色不同。

對於圖$G$，如果存在一個$k$種顏色的恰當染色方案，我們稱$G$是$k$染色的。在所有滿足條件的$k\in \mathbb {Z_{+}}$，稱最小的那個$k$為$\chi (G)$。

子圖

對於任意一個圖$G$和$G'$，如果$V(G')\subseteq V(G)$並且$E(G')\subseteq E(G)$，則稱$G'$是$G$的子圖，記為$G'\subseteq G$。若$G'\neq G$，則稱$G'$是$G$的真子圖，記為$G'\subset G$。

葉（lobe）

對於圖$G$即其一個點的子集$S\subseteq V(G)$。$G-S$有連通分支$G_{1},G_{2}\dots G_{t}$。對任意$G_{i}$，我們稱$S\cup G_{i}$在$G$中的導出子圖為$S$-葉（$S$-lobe）。

基本性質

1. $G$是一個沒有孤立點的色臨界圖，當且僅當對任意$e\in E(G),\ \chi (G-e)<\chi (G)$。

   證明："$\Rightarrow$"由定義可知顯然。"$\Leftarrow$"：由於$\forall G'\subset G,\exists e\in G-G'$。所以$\chi (G')\leq \chi (G-e)<\chi (G)$。

2. 設G是一個$k$-色臨界圖，則對任意$v\in V(G)$，存在一種使用$k$種顏色的恰當的染色方式使得$k-1$種顏色均出現在鄰域$N(v)$中。

   證明：由於色臨界圖的定義知，$\chi (G-v)<k$。所以存在一種使用前$k-1$種顏色對$G-v$的恰當的染色方式。然後再對$v$進行染色，則必須有$k-1$種顏色均出現在$N(v)$中，否則可以用前$k-1$種色中沒有在出現$N(v)$的顏色對$v$染色，那麼就得到用前$k-1$顏色對$G$染色的方法，與$\chi (G)=k$矛盾。

3. 設G是一個$k$-色臨界圖，則對任意$e\in E(G)$，任意使用$k-1$種顏色對$G-e$的恰當的染色方式均將$e$兩端點染成相同顏色。

   證明：如果存在一種使用$k-1$種顏色對$G-e$的恰當的染色方式使得$e$兩端點染成不同顏色，那麼這種方式同樣能對$G$使用，這樣與$\chi (G)=k$矛盾。

相關定理

狄拉克定理

任意一個$k$-色臨界圖均為$k-1$-邊連通的。

證明用到以下引理：

凱南（Kainen）引理

設$G$的最小染色數$\chi (G)>k$，並且$X,Y$是對$V(G)$的一個劃分。如果$X,Y$在$G$上導出子圖$G[X],G[Y]$均是$k$可染色的，那麼$G-G[X]-G[Y]$中至少有$k$條邊。

證明：

由於$G[X],G[Y]$均是$k$可染色的，可以把$X$劃分為$k$個獨立集$X_{1},X_{2},\dots ,X_{k}$，把$Y$劃分為$k$個獨立集$Y_{1},Y_{2},\dots ,Y_{k}$。如果$X,Y$之間邊少於$k$條，則對$G$進行染色。先對$X_{1},X_{2},\dots ,X_{k}$中的點染上$k$種顏色。再分別對$Y_{1},Y_{2},\dots ,Y_{k}$逐獨立集染色，並且染每個獨立集時，與其相鄰以及染完色的獨立集個數少於$k$個，所以可在$k$中顏色中選擇餘下某種對其恰當染色。這樣就對$G$使用$k$種顏色恰當染色，與$\chi (G)>k$矛盾。引理證明完畢。

回到原證明，如果$G$不是$k-1$-邊連通的。那麼存在$k-2$條邊$E'=\{e_{1},e_{2}\dots e_{k-1}\}$使得$G-E'$不是連通圖，取其一個連通分支$X$，令$Y=V(G)-X$。由於不連通性可知$G-G[X]-G[Y]$的邊皆屬$E'$。又$G$是色臨界圖，有$\chi (G[X])<k,\chi (G[Y])<k$，所以均是$k-1$可染色。利用凱南引理可知，$G-G[X]-G[Y]$的邊數至多是$k-1$，但$|E'|=k-2$，矛盾。

定理2：

如果$G$是$k$-色臨界圖，那麼$G$的割集均不是團。特別說明的是，如果$G$有一個割集含有兩個點$S=\{x,y\}$，那麼$xy\notin G$並且$G$存在一個$S$-葉$H$使得$\chi (H+xy)=k$。