跳转到内容

色临界图

维基百科,自由的百科全书

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

定义

[编辑]

如果图的任意一个真子图,其色數均满足,则称色临界图(英語:-critical graph)。[1]

相关定义

[编辑]

图染色数

[编辑]

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

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

子图

[编辑]

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

叶(lobe)

[编辑]

对于图即其一个点的子集有连通分支。对任意,我们称中的导出子图-叶(-lobe)。

基本性质

[编辑]
  1. 是一个没有孤立点的色临界图,當且僅當對任意
    证明:""由定义可知显然。"":由于。所以
  2. 设G是一个-色临界图,则對任意,存在一种使用种颜色的恰当的染色方式使得种颜色均出现在鄰域英语Neighbourhood (graph theory)中。
    证明:由于色临界图的定义知,。所以存在一种使用前种颜色对的恰当的染色方式。然后再对进行染色,则必须有种颜色均出现在中,否则可以用前種色中没有在出现的颜色对染色,那么就得到用前颜色对染色的方法,与矛盾。
  3. 设G是一个-色临界图,则对任意,任意使用种颜色对的恰当的染色方式均将两端点染成相同颜色。
    证明:如果存在一种使用种颜色对的恰当的染色方式使得两端点染成不同颜色,那么这种方式同样能对使用,这样与矛盾。

相关定理

[编辑]

狄拉克定理

[编辑]

任意一个-色临界图均为-邊連通英语k-edge-connected graph的。[1]:211

证明用到以下引理:

凯南(Kainen)引理

[编辑]

的最小染色数,并且是对的一个划分。如果导出子图均是可染色的,那么中至少有条边。[1]:211

证明:

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

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

定理2:

[编辑]

如果-色临界图,那么割集英语Cut (graph theory)均不是。特别说明的是,如果有一个割集含有两个点,那么并且存在一个-叶使得[1]

参考内容

[编辑]
  1. ^ 1.0 1.1 1.2 1.3 Douglas B.West. Introduction to Graph Theory. Pearson Enducation. : 210–220. ISBN 81-7808-830-4.