色临界图

数学分支图论中，色临界图或临界图（英语：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$。