第六章 图的着色

图的着色包括对边、顶点和平面区域的着色。本章只讨论简单图的顶点着色。图的着色包括对边、顶点和平面区域的着色。本章只讨论简单图的顶点着色。 第六章 图的着色 [例]假设要安排6个期末考试，要避免一个学生在同一天参加两个考试，试问最少需要安排几天进行期末考试？例如，用矩阵表示,(a , b)=1表示有学生同时参加a和b考试。

[解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。[解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。 a f b c e d 第六章 图的着色

[着色]图 G=(V,E) 的一个k顶点着色指用k种颜色对G的各顶点的一种分配方案。若着色使得相邻顶点的颜色都不同，则称该着色正常，或称G存在一个正常的k顶点着色（或称一个k着色）。此时称G为k-可着色的。 [色数]使 G=(V,E) k-可着色的最小k值称为G的色数，记为 (G)。若 (G)=k，称G为k色图。 6.1 色数

[例] 6.1 色数

特殊图的色数 ① 零图：(G)=1 ② 完全图Kn：(G)=n ③ G是一条回路：(G)=2 若|V|是偶数 (G)=3 若|V|是奇数 ④ G是一棵非平凡树： (G)=2 ⑤ (G)=2的充要条件是: (a) |E|1；(b) G中不存 在边数为奇数的回路。（此时G为二部图） ⑥ 若G1、G2为G的两个连通分支，则 (G)=max{(G1), (G2)} 6.1 色数

[定理]对G=(V,E)， =max{deg(vi)|viV}，则 (G)  +1。 [证明]对于结点数使用归纳法，证明G是(+1)-可着色的。 [定理] (Brooks)设G=(V,E) 是简单连通图，但不是完全图，不是奇数长度圈， =max{deg(vi)|viV}3，则 (G)  , 即G是-可着色的。 定理给出了色数的一个上限，但很不精确。Brooks定理也说明只存在两类满足(G) =+1的图。 [例]二部图可2着色，但是可以相当大。 6.1 色数

[Hajós猜想]若G是n色图，则G包含Kn的一个同胚图。[Hajós猜想]若G是n色图，则G包含Kn的一个同胚图。 n=1,2显然，n=3,4已证，其他未决 。 [四色猜想]任何平面图都是 4-可着色的。 由于存在着不可3-着色的平面图K4，4色问题若可证明，将是平面图色数问题的最佳结果。 [五色定理]任何简单平面图都是 5-可着色的。 [证明]（1890，Heaword） 6.1 色数

v1 v1 v5 v5 v2 v2 v v v3 v3 v4 v4 五色定理证明 对结点数n归纳。假定