色临界图

數學分支圖論中，色临界图或臨界圖（）是图染色问题中一类特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。

定义 
如果图的任意一个真子图，其色數均满足，则称为色临界图（）。

相关定义

图染色数 

对于给定的图，存在种颜色和一种染色方案，将图中每一个顶点都染成种颜色中的一种。如果染色方案满足一下条件，那么将称该染色方案为恰当的染色方案：对于图中任意两个顶点，如果，那么所染成的颜色不同。

对于图，如果存在一个种颜色的恰当染色方案，我们称是染色的。在所有满足条件的，称最小的那个为。

子图 
对于任意一个图和，如果并且，则称是的子图，记为。若，则称是的真子图，记为。

叶（lobe） 
对于图即其一个点的子集。有连通分支。对任意，我们称在中的导出子图为-叶（-lobe）。

基本性质 
是一个没有孤立点的色临界图，當且僅當對任意。
证明：""由定义可知显然。""：由于。所以。
设G是一个-色临界图，则對任意，存在一种使用种颜色的恰当的染色方式使得种颜色均出现在中。
证明：由于色临界图的定义知，。所以存在一种使用前种颜色对的恰当的染色方式。然后再对进行染色，则必须有种颜色均出现在中，否则可以用前種色中没有在出现的颜色对染色，那么就得到用前颜色对染色的方法，与矛盾。
设G是一个-色临界图，则对任意，任意使用种颜色对的恰当的染色方式均将两端点染成相同颜色。
证明：如果存在一种使用种颜色对的恰当的染色方式使得两端点染成不同颜色，那么这种方式同样能对使用，这样与矛盾。

相关定理

狄拉克定理
任意一个-色临界图均为-的。

证明用到以下引理：

凯南（）引理 
设的最小染色数，并且是对的一个划分。如果在上导出子图均是可染色的，那么中至少有条边。

证明：

由于均是可染色的，可以把划分为个独立集，把划分为个独立集。如果之间边少于条，則对进行染色。先对中的点染上种颜色。再分别对逐独立集染色，并且染每个独立集时，与其相邻以及染完色的独立集个数少于个，所以可在中颜色中选择餘下某种对其恰当染色。这样就对使用种颜色恰当染色，与矛盾。引理证明完毕。

回到原证明，如果不是-边连通的。那么存在条边使得不是连通图，取其一个连通分支，令。由于不连通性可知的邊皆屬。又是色临界图，有，所以均是可染色。利用凯南引理可知，的邊數至多是，但，矛盾。

定理2： 
如果是-色临界图，那么的均不是團。特别说明的是，如果有一个割集含有两个点，那么并且存在一个-叶使得。

参考内容

图族
图染色