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