交错路调色法 从5色定理到Brooks'定理
交错路调色法 从5色定理到Brooks’ 定理
如果有人声称图论中的某个问题被外界所熟悉，那一定是指下面的四色定理 (four colour theorem)(这个定理蕴含着：每个地图最多只需四种颜色来着色)： 定理5.1.1（四色定理）每个可平面图是4可着色的 关于四色定理证明的一些讨论和其历史，可以参考这一章最后的注解.在这里， 我们证明下面较弱的形式 定理5.1.2（五色定理）每个可平面图是5可着色的. 证明设G是一个有n≥6个顶点和m条边的平面图.我们归纳地假设，有 个具有少于n个顶点的平面图均是5可着色的.由推论4.2.10，有 dG=2m≤23n-6 1<6. 个人研使用 设v∈G是顶点度不大于5的顶点.由归纳假设知，图H:=G一v存在一个顶点 着色V(H)一{1，·，5.如果v的邻点最多用了4种颜色，那么c可以扩充为 图G的一个5着色.所以我们可以假设顶点v恰有5个邻点，且每个邻点着有不 同的颜色 设D是一个足够小的包含v的开圆盘，使得它只与关联v的五条边的直线 段相交.我们按照这些线段在D中的循环位置列举为1，·，s5,并且假设v是 包含s:的边（亿=1，·，5，见图51.1）.不失一般性，我们可以假设对于每个，有 c()=i
首先证明每条1-g路PCH一{2，v4}在H中把2和4分开.显然，这 个结论成立当且仅当在G中的圈C:=v1Pu3v把U2和v4分开，我们可通过说明 2和4在C的不同面中来证明这个结论 我们在D中分别选取s2和94的内点2和x4,那么在D八(s1Us3)CR2\C 中，每一个点都可以通过一条多边弧连接到x2或x4,这说明x2和x4(因此2和 4也是一样)在C的不同面中，否则，D只与C的两个面中的一个相交，这与v属 于这两个面的边界这一事实矛盾（定理4.11）. 给定i,j∈{L,·,5},设H)是由着色i和j的顶点所导出的H的子图.我 们可以假设H1,3中包含1的分支C也包含g,如果把C中所有着色1和3的 顶点交换颜色，我们就得到了H的另一个5着色.如果3生C,那么在这个新着 色中，1和3都着色3，这时我们可以给v着色1.因此，H1.3包含一条1-仍路 P.上面已经证明，在H中P把2和v4分开.因为PnH2,4=②，这意味着2和 4属于H2,4的不同分支.在包含2的那个分支里，交换颜色2和4，因此把2重 新着色为4.现在就没有着色2的邻点，我们可以给它着此色了： ▣
给定一个图，我们怎样来决定它的色数呢？怎样才能找到一个使用尽可能少颜 色的顶点着色呢？色数与图的其他不变量（例如平均度、连通度或者围长）的关系 是怎样的呢？ 从色数的定义，我们可以直接得到下面这个上界 命题5.2.1每个具有m条边的图满足 1 xg≤2+V2m+4 证明设c是图G中一个具有k=X(G)种颜色的顶点着色，那么在G的每 两个色类之间都至少存在一条边，否则，我们可以把这两个色类着同一种颜色.因 此m≥。k(化-1).从这个不等式中解出k,就得到了我们想要的结论. 0
一个明显的不用太多颜色来着色图的方法是下面的贪婪算法(greedy algorithm): 从图G的一个固定顶点序列，…，开始，依次考虑顶点，给每个顶点贴着第 一个可用的颜色，比如，在1，·，-1中，找到的邻点中还未用过的最小正整 数来给顶点着色.用这种方法，永远不会使用多于△(G)+1种颜色，即使对选 择不当的序列1，.，n也是一样，如果G是完全图或者奇圈，那么这是最好可 能的