3.10 顶点着色与边着色

顶点着色与边着色

顶点着色

定义

图 G 的一种着色：给图 G 的每个顶点涂上一种颜色，使相邻顶点具有不同颜色。

• G 是 k 可着色的：能用 k 种颜色给 G 的顶点着色。
• 色数 $\chi (G)=k$：G 是 k 可着色的，但不是 $(k-1)$ 可着色的。色数为 k 的图称为 k 色图。

基本结果

1. χ(G) = 1 当且仅当 G 为零图。
2. $\chi (K_n)=n$。
3. 偶圈的色数为 2，奇圈色数为 3。奇阶轮图 $\chi (W_n)=3$，偶阶轮图 $\chi (W_n)=4$。
4. 若 G 的边集非空，则 $\chi (G)=2$ 当且仅当 G 为二部图。

上界定理

定理：对于任意无环图 G，均有 $\chi (G)\le \Delta (G)+1$。

Brooks定理（1941）：若 G是连通的简单图，并且它既不是奇圈又不是完全图，则 $\chi (G)\le \Delta (G)$。

次大度：设 G 是至少有一条边的简单图，定义： - V₂(G) = {v ∈ V(G) | N(v)中存在点 u满足 d(u) ≥ d(v)} $-{\Delta }_2(G)=\max d(v)|v\in V_2(G)$ 称 ${\Delta }_2(G)$为 G的次大度。

定理：设 G是非空简单图，则 $\chi (G)\le {\Delta }_2(G)+1$。

推论：设 G是非空简单图，若 G中最大度点互不邻接，则 $\chi (G)\le \Delta (G)$。

希伍德定理：每个平面图是 5 可着色的。

地图着色

地图：连通无桥平面图（嵌入）与所有的面。国家即地图的面。两个国家相邻若它们的边界至少有一条公共边。

地图的面着色可转化为对偶图的点着色。

定理：地图 G 是 k 面可着色的当且仅当它的对偶图 G* 是 k 点可着色的。

排课表问题

将课程建模为图的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。用同一种颜色给同一时段的课程顶点染色，问题转化为求图的色数。

边着色

定义

正常边着色：对图 G 的边进行染色，相邻边染不同颜色。G 是 k 边可着色的 指能用 k 种颜色进行正常边着色。

边色数 χ’(G)：正常边着色需要的最少颜色数。

对图的正常边着色实际上是对 G 的边集合的一种划分，每个划分块是 G 的一个边独立集（无环时是匹配）。边色数对应图的最小独立集划分数。

二部图的边色数

定理（哥尼，1916）：若 G是二部图，则 ${\chi }^{\prime }(G)=\Delta (G)$。

一般图的边色数

维津定理（Vizing，1964）：若 G是简单图，则 ${\chi }^{\prime }(G)=\Delta (G)$或 ${\chi }^{\prime }(G)=\Delta (G)+1$。

定理：设 G是简单图且 $\Delta (G)>0$。若 G中只有一个最大度点或恰有两个相邻的最大度点，则 ${\chi }^{\prime }(G)=\Delta (G)$。

定理：设 G是简单图。若点数 $n=2k+1$且边数 $m>k\Delta$，则 ${\chi }^{\prime }(G)=\Delta (G)+1$。

定理：设 G是奇数阶 $\Delta$正则简单图，若 $\Delta >0$，则 ${\chi }^{\prime }(G)=\Delta (G)+1$。

一般维津定理：设无环图 G中边的最大重数为 $\mu$，则 ${\chi }^{\prime }(G)\le \Delta (G)+\mu$。

排课表问题的边着色模型

有 m 位教师、n 个班级，教师 xᵢ 要给班级 yⱼ 上 pᵢⱼ 节课。令 X = {x₁, …, xₘ}，Y = {y₁, …, yₙ}，xᵢ 与 yⱼ 间连 pᵢⱼ 条边，得二部图 G = <X, Y, E>。问题转化为将 E 划分为互不相交的最小匹配数，即求图的边色数。

链接到

• 上一个知识点：3.9 支配集覆盖集独立集匹配
• 下一个知识点：无（本章最后一个知识点）