图论讲义6染色理论VIP免费

1 第六章 染色理论 许多实际问题可以归结为求图的匹配或者独立集。此外，在许多应用中，人们希望知道：一个给定的图，它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。 §6 .1 点染色 定义 6 .1 .1 设 G 是一个无环边的图。G 的顶点正常 k 染色(proper vertex k-colouring)π 是指 k种颜色k，，，L21对于 G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。换句话说，G 的顶点正常 k 染色π 是一个映射 },,2,1{)(:kGVL→π, 使得)(1 i−π是独立集或空集),,2,1(kiL=. 注：设π 是G 的一个顶点正常 k 染色。令 })(|)({)(V1ixGVxii=∈==−ππ，（ki,,2,1L=）。 则 π 实际上是对顶点集)(GV的一种划分：),,,(21kVVVL=π，其中φ=jiVV I，)(1GVVkii ==U，且每个iV 是独立集或空集),,2,1(kiL=. 例： 定义 6 .1 .2 若存在G 的一种顶点正常 k 染色，则称图G 是点 k 色可染的(vertex k-colourable)， 有时简称为k 色可染的或可 k 染色的。 注：⑴ 每个图G 一定是)(Gν色可染的。 ⑵ 若图G 是k 色可染的，则对任何正整数km ≥，G 也m 色可染。 定义 6 .1 .3 设 G 是无环边的图，令 GkG|min{)(=χ是k 色可染的} ， 称)(Gχ为G 的点色数，有时简称为色数(chromatic number) 。若kG =)(χ，则称 G 为k 色图(k-chromatic graph)。 3 1 3 2 21 3 112 2注： （1） 若kG =)(χ（即G 是k 色图），则G 中任何点k 染色),,,(21kVVVL=π中每个iV 都是非空的独立集。换言之，G 的色数是G 中点不交的独立集的最小数目。 （2）易证：  1)(=Gχ⇔νKG =；  2)(=Gχ⇔ G 是非空二部图；  )()(GGνχ=⇔νKG ⊇。 （3）3)(12=+nCχ。 （4） 3)(≥Gχ⇔ G 含有奇圈。 （5）四色定理：对任何平面图G，4)(≤Gχ。 点染色理论的基本问题：给定图G，确定)(Gχ的值。 研究现状：对一般情况，给出了)(Gχ的范围（用G 的参数表示）；对某些特殊图类，确定出了)(Gχ的确切值。 定义6 .1 .4 设)1(,)(≥=kkGχ。若对G 的任何真子图H，均有kH <)(χ，则称G 是临界k 色图（critical k-chromatic graph）. 注：（1）G 是临界1 色图⇔1GK≅； G 是临界2 色图⇔2GK≅； G 是临界3 色图⇔ G 是奇圈； （2）Grótz sch 图是临界4 色图； G...