數學分支圖論中，色临界图或臨界圖（）是图染色问题中一类特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。
定义
如果图G的任意一个真子图G'\subset G，其色數均满足\chi(G')，则称G为\chi(G)色临界图（）。
相关定义
图染色数
对于给定的图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）。
基本性质
#G是一个没有孤立点的色临界图，當且僅當對任意e\in E(G),\ \chi(G-e)。
#:证明："\Rightarrow "由定义可知显然。"\Leftarrow"：由于\forall G'\subset G, \exists e\in G-G'。所以\chi(G')\le \chi(G-e)。
#设G是一个k-色临界图，则對任意v\in V(G)，存在一种使用k种颜色的恰当的染色方式使得k-1种颜色均出现在N(v)中。
#:证明：由于色临界图的定义知，\chi(G-v)。所以存在一种使用前k-1种颜色对G-v的恰当的染色方式。然后再对v进行染色，则必须有k-1种颜色均出现在N(v)中，否则可以用前k-1種色中没有在出现N(v)的颜色对v染色，那么就得到用前k-1颜色对G染色的方法，与\chi(G)=k矛盾。
#设G是一个k-色临界图，则对任意e\in E(G)，任意使用k-1种颜色对G-e的恰当的染色方式均将e两端点染成相同颜色。
#:证明：如果存在一种使用k-1种颜色对G-e的恰当的染色方式使得e两端点染成不同颜色，那么这种方式同样能对G使用，这样与\chi(G)=k矛盾。
相关定理
狄拉克定理
任意一个k-色临界图均为k-1-的。
证明用到以下引理：
凯南（）引理
设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-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。
参考内容
评论 (0)