第七章 图的着色

一、图的边着色

(一)、相关概念

现实生活中很多问题，可以模型为所谓的边着色问题来处理。例如排课表问题。

定义1 设G是图，对G的边进行染色，若相邻边染不同颜色，则称对G进行正常边着色；

定义2 设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为\(\chi^\prime(G)\)：

在对G正常边着色时，着相同颜色的边集称为该正常着色的一个色组。

(二)、几类特殊图的边色数

1、偶图的边色数

定理1

\(\Delta\)是最大度

? 定义3 设п是G的一种正常边着色，若点u关联的边的着色没有用到色i，则称点u缺i色。

定理2 (哥尼，1916)若G是偶图，则

2、一般简单图的边色数

引理：设G是简单图，x与y1是G中不相邻的两个顶点，п是G的一个正常k边着色。若对该着色п，x,y1以及与x相邻点均至少缺少一种颜色，则G+xy1是k边可着色的。

定理3 (维津定理，1964) 若G是单图，则：

3、三类特殊简单图的边色数

定理4 设G是单图且Δ(G)>0。若G中只有一个最大度点或恰有两个相邻的最大度点，则：

定理5 设G是单图。若点数n=2k+1且边数m>kΔ,则：

定理6 设G是奇数阶Δ正则单图,若Δ>0,则：

(三)、边着色的应用

二、图的顶点着色

(一)、相关概念

定义1 设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色；

如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；

对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用\(\chi(G)\)表示。

注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图G正常着色，称为对图G的最优点着色。

(二)、图的点色数的几个结论

定理1 对任意的图G，有：

定理2(布鲁克斯，1941) 若G是连通的单图，并且它既不是奇圈，又不是完全图，则：

定理3 设G是非空简单图，则：

\(\Delta_2(G)\)为图G的次大度

推论：设G是非空简单图，若G中最大度点互不邻接，则有：

(三)、四色与五色定理

给一张平面地图正常着色，至少需要4种颜色。这就是著名的4色定理。

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

根据平面图和其对偶图的关系，上面定理等价于每个平面图是5可顶点正常着色的。

(四)、顶点着色的应用

四、色多项式

(一)、色多项式概念

所谓色计数，就是给定标定图G和颜色数k,求出正常顶点着色的方式数。方式数用\(P_k(G)\)表示。\(P_k(G)\)是k的多项式，称为图G的色多项式。

(二)、色多项式的两种求法

1、递推计数法

定理1 设G为简单图，则对任意\(e∈E(G)\) 有：

2、理想子图计数法

定义1：设H是图G的生成子图。若H的每个分支均为完全图，则称H是G的一个理想子图。用\(N_r(G)\)表示G的具有 r 个分支的理想子图的个数。

定理2 设\(q_r(G)\)表示将单图G的顶点集合V划分为 r 个不同色组的色划分个数，则：

上面定理2实际上给我们提供了色多项式的求法：用k种颜色对单图G正常着色，可以这样来计算着色方式数：色组为1的方式数+色组为2的方式数+…+色组为n的方式数。即有如下计数公式：

(三)、色多项式的性质

若图G有环或有重边，则去掉环并将重边用单边代替之 后所得图的k着色数目与原图一样

定理4 n阶单图G的色多项式Pk(G)是常数项为0的首1整系数多项式，且各项系数符号正负相间。

设e=uv是图G的一条边，并且d(u)=1，则 Pk(G)=(k-1)Pk(G-u)

\(G\cdot e\) 表示图G按e收缩

\(N_r(G)\) 表示G的具有 r 个分支的理想子图的个数。