交错路调色法 从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是完全图或者奇圈，那么这是最好可 能的
一般而言，即使是对于贪梦着色，这个上界△+1仍然是很大.事实上，用上面 的算法对顶点，着色时，我们只需要dG1…,()+1种颜色，而不是dG()+1 种颜色，就可以进行下去.注意到，这个时候，对于方>，算法忽略了的邻点 u,因此对于大多数图而言，有着很大的空间去改进△+1这个上界，这可以通过 选择一个特别有利的顶点顺序来开始着色：先选择那些顶点度比较大的顶点（这 时大部分邻点被忽略)，最后选择那些顶点度比较小的顶点.局部来看，如果是 Gu,·,中度数最小的顶点，则我们需要的dG,()+1种颜色也是最少 的，这可以容易地实现，只需要首先选取具有d(u)=(G)的顶点m,然后再取图 G一vm中度数最小的顶点作为-1，依次进行下去. 找个最小的k使得图G有这样一个顶点序列，使得它的每个顶点只有少于 个邻点排在它前面，这个k就叫做G的着色数(colouring number),记为col(G).我 们上面刚刚讨论的序列表明col(G)≤maXHCG6(H)+1.但是对于HCG,因为在 H的任意序列中，最后的那个顶点的“向后度数”就是它在H中的原来度数，它至 少为(H),所以显然有col(G)≥col(H)和col(0≥(H)+1.因此我们证明了下 面的结论 命题5.2.2 每个图G满足 X(G)≤col(G)=max{δ(H|HcG+1
我们已经看到，对每个满足x(G)≤△(G+1的图G,等号在完全图和奇圈时 成立.对于其他情况，这个一般的界可以作少许的改进， 定理5.2.4(Brooks,1941)设G是一个连通图.如果G既不是完全图，也不 是奇圈，那么 x(G)≤△(G) 证明我们对G使用归纳法.如果△(G≤2，那么G是一条路或一个圈 结论显然成立.因此假设△：=△(G)≥3，并且结论对于顶点数较小的图都成立， 假设X(G△：止个人 设v是G的一个顶点，令H:=Gu,由归纳假设知，X(H)≤△，并且对H的 每个分支H'有X(H)≤△(H)≤△，除非H'是完全图或是奇圈，在这种情况下， 有X(H)=△(H)+1≤△，这是因为H印的每个顶点在中都具有最大度，并且 这样一个顶点和，在G中也是相邻的， 因为H可以△着色但G不能，所以我们有下面的结论： H的每个△-着色，在v的邻点使用了所有的颜色1，·，△. (1) 特别地，d(v)=△
给定H的任何一个△-着色，我们用表示v的着色i的邻点(=1，…，△) 对i≠j,用H,表示由着色i或j的顶点所导出的H的子图 对于所有i≠j,顶点和U在H的同一个分支C中 (2) 否则，我们可以在其中的一个分支中交换i和j的颜色，从而”和可以着同一 种颜色，与(1)矛盾。 C总是一条-U)路 (3) 确实，令P是C中一条U路，因为dH()≤△-1，所以贴的所有邻点着两 两不同的颜色，否则，我们可以重新给，着色，与(1)矛盾.因此，P上的邻点 也是它在C上的唯一邻点；对u有同样的结论.所以，若C≠P,那么在H中 P包含一个内部顶点，它有三个着同样颜色的邻点，让u是P上第一个这样的顶 点（图5.2.1），因为u的邻点至多用了△-2种颜色，所以我们可以重新给u着色. 但这使得Pu成了H中的一个分支，与(2)矛盾
对不同的i,,k,路C和路C,k只在相交 (4) 这是因为，如果：≠u∈C)∩C,k,那么u分别有两个着j的邻点和两个着k的 邻点，因此我们可以重新给“着色.在新的着色中，，和在H,的不同分支中， 与2)矛盾.世个人科开数之伟用
现在，这个定理的证明可以容易地得到.如果v的邻点是两两相邻的，那么在 N(o)U{w}中的每个顶点都已经有△个邻点了，所以G=GN(o)U{uI=K△+1 因为G是完全图，结论成立.所以我们可以假设2生G,这里1，·，v△来自H 的某个固定△-着色c.设u≠2是在路C,2上的邻点，那么c(u)=2.交换 C,3中颜色1和3，我们得到H的一个新着色c,设，H,和C%,等是关于C 的类似记号.因为c(u)=c(u)=2,所以作为=喝的邻点，u现在属于C23·然 而由(4)关于c知，路C,2保留它原来的着色，所以u∈C,2CC12·因此u∈ C23nC12,这与关于d的(4矛盾 日