數學分支圖論中,色临界图或臨界圖(英語:critical graph)是图染色问题中一类特殊的圖,從此類圖中,移除任何一邊或一點,皆會使圖的色數減少。这一类图具有一些非常好的性质,能在很多证明定理中发挥用处。
如果图
的任意一个真子图
,其色數均满足
,则称
为
色临界图(英語:
-critical graph)。[1]
对于给定的图
,存在
种颜色和一种染色方案,将图中
每一个顶点都染成
种颜色中的一种。如果染色方案满足一下条件,那么将称该染色方案为恰当的染色方案:对于图
中任意两个顶点
,如果
,那么
所染成的颜色不同。
对于图
,如果存在一个
种颜色的恰当染色方案,我们称
是
染色的。在所有满足条件的
,称最小的那个
为
。
对于任意一个图
和
,如果
并且
,则称
是
的子图,记为
。若
,则称
是
的真子图,记为
。
对于图
即其一个点的子集
。
有连通分支
。对任意
,我们称
在
中的导出子图为
-叶(
-lobe)。
是一个没有孤立点的色临界图,當且僅當對任意
。
- 证明:"
"由定义可知显然。"
":由于
。所以
。
- 设G是一个
-色临界图,则對任意
,存在一种使用
种颜色的恰当的染色方式使得
种颜色均出现在鄰域
中。
- 证明:由于色临界图的定义知,
。所以存在一种使用前
种颜色对
的恰当的染色方式。然后再对
进行染色,则必须有
种颜色均出现在
中,否则可以用前
種色中没有在出现
的颜色对
染色,那么就得到用前
颜色对
染色的方法,与
矛盾。
- 设G是一个
-色临界图,则对任意
,任意使用
种颜色对
的恰当的染色方式均将
两端点染成相同颜色。
- 证明:如果存在一种使用
种颜色对
的恰当的染色方式使得
两端点染成不同颜色,那么这种方式同样能对
使用,这样与
矛盾。
任意一个
-色临界图均为
-邊連通的。[1]:211
证明用到以下引理:
设
的最小染色数
,并且
是对
的一个划分。如果
在
上导出子图
均是
可染色的,那么
中至少有
条边。[1]:211
证明:
由于
均是
可染色的,可以把
划分为
个独立集
,把
划分为
个独立集
。如果
之间边少于
条,則对
进行染色。先对
中的点染上
种颜色。再分别对
逐独立集染色,并且染每个独立集时,与其相邻以及染完色的独立集个数少于
个,所以可在
中颜色中选择餘下某种对其恰当染色。这样就对
使用
种颜色恰当染色,与
矛盾。引理证明完毕。
回到原证明,如果
不是
-边连通的。那么存在
条边
使得
不是连通图,取其一个连通分支
,令
。由于不连通性可知
的邊皆屬
。又
是色临界图,有
,所以均是
可染色。利用凯南引理可知,
的邊數至多是
,但
,矛盾。
如果
是
-色临界图,那么
的割集均不是團。特别说明的是,如果
有一个割集含有两个点
,那么
并且
存在一个
-叶
使得
。[1]