第五节着色问题

第五节着色问题定义1.图G的顶点着色(VerterColouring)是给每个顶点赋予一种颜色，使得相邻顶点的颜色不同，给图G进行顶点着色需要的颜色的最小值称为G的色数(ChromaticNumber)，记为)(G.若)(G，则称G是-色的(κ-chromatic)；若)(G，则称G是可-着色的(κ-colourable).例1.在下图中2)(1G，3)(2G，4)(3G.注意1G即为2，2G即为5111111111111111111v1v2v1v2u1u2ωG1G2G3v1v2v3v4v5u1u3u4u5ω11u211111111111下面讨论)(G的上界和下界，先给出下面的定义.定义2.图G中两两不相邻的顶点组成的集合称为独立集(IndependentSet)，用)(G来表示G中最大独立集的元素个数.图G中两两相邻的顶点构成的集合称为团(Clique)，用)(G表示G中最大团的元素个数.注记：（1）显然，G是可-着色的当且仅当)(GV是个独立集的并.特别的，G是可2-着色的当且仅当G是二部图.（2）)()(GG且)()()(GGnG（习题1）.（3）对于完全图n有：nnn)()(.但一般来说)(G可以远大于)(G.下面介绍一种构造任意色数的三角形无关图（即不含3为子图）的方法，这种方法归功于Mycielski,1955.定义3(Mycielski构造).由简单图G产生一个以G为子图的简单图'G.从顶点集为}v,...,v,{vn21的图G开始添加顶点}u,...,u,{un21和；添加边，使得iu与)(iGvN中的顶点相邻，与}u,...,u,{un21中的所有顶点相邻.例1中，以2-色图1G开始，进行二次Mycielski构造，分别得到3-色图2G和4-色图3G.下面的定理告诉我们可以构造一个色数任意大的图G且2)(G.定理1(Mycielski1955).由一个-色三角形无关图G，Mycielski构造可得到一个1-色三角形无关图'G.定义4.图G称为-临界的(κ-critical)，如果)(G且1)(vG))((GVv.也即去掉G的任何一个顶点会使G的色数减少.下面介绍-临界图的一个重要性质.定理2.如果G是-临界的，则1)(G.证明：令G是-临界的且2)(G.设)(GVv且)()(Gvd.由于G是-临界的，故1)(vG.由于2)(vd，故在对vG着色的1种颜色中，存在一种颜色没有被v的至多2个邻接点使用，将这种颜色对v着色就得到G是1-着色的.与)(G矛盾.推论①：如果)(G，则G至少有个顶点的度数不小于1.证明：如果)(G，则G就有一个-临界子图H（删除G中不影响)(G的顶点，直到不能继续为止）.由于H)(，故H至少有个顶点.由定理2，1)H(，所有H至少有个顶点的度数不小于1，即这个顶点在G中的度数不小于1.推论②：1)()(GG.证明：假设1)()(GG，即)(1)(GG，与定理2矛盾.上述推论中的等号在G是完全图或奇环时成立，除这两类图之外，我们有下面的结论.定理3(Brooks,1941).如果G是连通图，并且G既不是完全图也不是奇环，则)()(GG.习题：1.证明：)()(GG且)()()(GGnG2.下列各图是否可以3-着色？确定它们的色数.gfedcabfedbacda1111111111b1e11111111111111c111111111113.新学期安排补考，下表是上学期考试不及格的情况.“×”表示某门课不及格.学生数分高代解析几何英语张三××李四××王五××赵六×××陈七××问至少需要安排几场考试，使得这五个同学参加完所有的考试（注：每场考试一个学生只能考一门，但考场中的学生可以考不同的科目）4.如果G的度序列为nddd...21，则}1,{minmax1)(},..,1{idGini.5.图G的边着色是指将颜色赋予G的边，如果相邻边的颜色不同，则称这种边着色为正常边着色(properedgecolouring).边色数记为)('G，是对G进行正常边着色所需要的最小颜色数量.①证明：)()('GG.举例说明某些图可以取到下界.②证明：对于完全图12n，12)('12nn；对完全图n2，有12)('2nn（因此对于任意完全图n，有nnnnn1)()('1)(.这个结果不是偶然的，因为更强的一个结果(Vizing定理)是：对任意图G，1)()(')(GGG）③证明：如果G是二部图，则)()('GG(Konig,1916).