《第五节 着色问题.doc》由会员分享，可在线阅读，更多相关《第五节 着色问题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、第五节 着色问题定义1. 图的顶点着色(Verter Colouring)是给每个顶点赋予一种颜色，使得相邻顶点的颜色不同，给图进行顶点着色需要的颜色的最小值称为的色数(Chromatic Number)，记为. 若，则称是-色的(-chromatic)；若，则称是可-着色的(-colourable).例1. 在下图中，. 注意即为，即为下面讨论的上界和下界，先给出下面的定义.定义2. 图中两两不相邻的顶点组成的集合称为独立集(Independent Set)，用来表示中最大独立集的元素个数. 图中两两相邻的顶点构成的集合称为团(Clique)，用表示中最大团的元素个数.注记：（1）显然，是可
2、-着色的当且仅当是个独立集的并. 特别的，是可2-着色的当且仅当是二部图.（2）且（习题1）.（3）对于完全图有：. 但一般来说可以远大于. 下面介绍一种构造任意色数的三角形无关图（即不含为子图）的方法，这种方法归功于Mycielski,1955.定义3(Mycielski构造). 由简单图产生一个以为子图的简单图. 从顶点集为的图开始添加顶点和；添加边，使得与中的顶点相邻，与中的所有顶点相邻.例1中，以2-色图开始，进行二次Mycielski构造，分别得到3-色图和4-色图. 下面的定理告诉我们可以构造一个色数任意大的图且.定理1(Mycielski 1955). 由一个-色三角形无关图，M
3、ycielski构造可得到一个-色三角形无关图.定义4. 图称为-临界的(-critical)，如果且.也即去掉的任何一个顶点会使的色数减少.下面介绍-临界图的一个重要性质.定理2. 如果是-临界的，则.证明：令是-临界的且. 设且. 由于是-临界的，故.由于，故在对着色的种颜色中，存在一种颜色没有被的至多个邻接点使用，将这种颜色对着色就得到是-着色的. 与矛盾.推论：如果，则至少有个顶点的度数不小于.证明：如果，则就有一个-临界子图H（删除中不影响的顶点，直到不能继续为止）.由于，故H至少有个顶点. 由定理2，所有H至少有个顶点的度数不小于，即这个顶点在中的度数不小于.推论：.证明：假设，即
4、，与定理2矛盾.上述推论中的等号在是完全图或奇环时成立，除这两类图之外，我们有下面的结论.定理3(Brooks,1941). 如果是连通图，并且既不是完全图也不是奇环，则.习题：1. 证明：且2. 下列各图是否可以3-着色？确定它们的色数.3. 新学期安排补考，下表是上学期考试不及格的情况.“”表示某门课不及格.学生数分高代解析几何英语张三李四王五赵六陈七问至少需要安排几场考试，使得这五个同学参加完所有的考试（注：每场考试一个学生只能考一门，但考场中的学生可以考不同的科目）4. 如果的度序列为，则.5. 图的边着色是指将颜色赋予的边，如果相邻边的颜色不同，则称这种边着色为正常边着色(proper edge colouring). 边色数记为，是对进行正常边着色所需要的最小颜色数量.证明：.举例说明某些图可以取到下界.证明：对于完全图，；对完全图，有（因此对于任意完全图，有. 这个结果不是偶然的，因为更强的一个结果(Vizing定理)是：对任意图，）证明：如果是二部图，则(Konig,1916).
