数学分支图论中,色临界图或临界图(英语:critical graph)是图染色问题中一类特殊的图,从此类图中,移除任何一边或一点,皆会使图的色数减少。这一类图具有一些非常好的性质,能在很多证明定理中发挥用处。
如果图
的任意一个真子图
,其色数均满足
,则称
为
色临界图(英语:
-critical graph)。[1]
相关定义[编辑]
图染色数[编辑]
对于给定的图
,存在
种颜色和一种染色方案,将图中
每一个顶点都染成
种颜色中的一种。如果染色方案满足一下条件,那么将称该染色方案为恰当的染色方案:对于图
中任意两个顶点
,如果
,那么
所染成的颜色不同。
对于图
,如果存在一个
种颜色的恰当染色方案,我们称
是
染色的。在所有满足条件的
,称最小的那个
为
。
对于任意一个图
和
,如果
并且
,则称
是
的子图,记为
。若
,则称
是
的真子图,记为
。
叶(lobe)[编辑]
对于图
即其一个点的子集
。
有连通分支
。对任意
,我们称
在
中的导出子图为
-叶(
-lobe)。
基本性质[编辑]
是一个没有孤立点的色临界图,当且仅当对任意
。
- 证明:"
"由定义可知显然。"
":由于
。所以
。
- 设G是一个
-色临界图,则对任意
,存在一种使用
种颜色的恰当的染色方式使得
种颜色均出现在邻域
中。
- 证明:由于色临界图的定义知,
。所以存在一种使用前
种颜色对
的恰当的染色方式。然后再对
进行染色,则必须有
种颜色均出现在
中,否则可以用前
种色中没有在出现
的颜色对
染色,那么就得到用前
颜色对
染色的方法,与
矛盾。
- 设G是一个
-色临界图,则对任意
,任意使用
种颜色对
的恰当的染色方式均将
两端点染成相同颜色。
- 证明:如果存在一种使用
种颜色对
的恰当的染色方式使得
两端点染成不同颜色,那么这种方式同样能对
使用,这样与
矛盾。
相关定理[编辑]
狄拉克定理[编辑]
任意一个
-色临界图均为
-边连通的。[1]:211
证明用到以下引理:
凯南(Kainen)引理[编辑]
设
的最小染色数
,并且
是对
的一个划分。如果
在
上导出子图
均是
可染色的,那么
中至少有
条边。[1]:211
证明:
由于
均是
可染色的,可以把
划分为
个独立集
,把
划分为
个独立集
。如果
之间边少于
条,则对
进行染色。先对
中的点染上
种颜色。再分别对
逐独立集染色,并且染每个独立集时,与其相邻以及染完色的独立集个数少于
个,所以可在
中颜色中选择馀下某种对其恰当染色。这样就对
使用
种颜色恰当染色,与
矛盾。引理证明完毕。
回到原证明,如果
不是
-边连通的。那么存在
条边
使得
不是连通图,取其一个连通分支
,令
。由于不连通性可知
的边皆属
。又
是色临界图,有
,所以均是
可染色。利用凯南引理可知,
的边数至多是
,但
,矛盾。
定理2:[编辑]
如果
是
-色临界图,那么
的割集均不是团。特别说明的是,如果
有一个割集含有两个点
,那么
并且
存在一个
-叶
使得
。[1]
参考内容[编辑]