图论-色数

设 \(G\) 是一个图， \(G\) 的色数定义为为顶点染色需要的最小颜色数，使得任意相邻的两个顶点颜色不同，一般记作 \(\chi(G)\)

常用的色数是二部图色数为 \(2\) 。我们有 \(Brooks\) 定理：

（弱化版）设 \(G\) 是图，则 \(\chi (G)\le \Delta(G)+1\)

任意染色，给 \(v_i\) 着色时，至多 \(\Delta(G)\) 个与它相邻的点用掉了 \(\Delta(G)\) 种颜色，所以它一定还有一种颜色可染。

（稍微强一点点的版本）若存在一个顶点度数不超过 \(\Delta(G)-1\) ，则 \(\chi (G)\le \Delta(G)\)

我们为顶点排序 \(v_1,v_2,...,v_n\) ，使得 \(d(v_1)\le \Delta(G)-1\) ，而其余的顶点 \(v_i\) 至少与 \(v_1,v_2,...,v_{i-1}\) 中一个相邻（由图的连通性，随便找一个 \(v_1,v_2,...,v_{i-1}\) 的邻点即可）

现在依次染色 \(v_n,v_{n-1},...,v_1\) ，每个点至多 \(\Delta(G)-1\) 个邻点被染色（因为每个点后面都有一个它的邻点尚未被染色），所以 \(\Delta(G)\) 种颜色足够了。

相同的思想可以证明一些染色问题：比如说 \(n\) 个顶点 \(m\) 条边，可以用 \(k\) 种颜色染点，使得至多 \(\frac mk\) 条边端点颜色相同。

最终版本：连通图 \(G\) 只要不是奇圈或完全图，则满足 \(\chi(G)\le \Delta(G)\)

我们只考虑 \(\Delta(G)\ge 3\) ， \(\Delta(G)\le 2\) 情况显然。

这个证明比前面的两个难了很多很多！我们还是要进行排序 \(v_1,v_2,...,v_n\) 使得 \(v_1v_2\) 不是边， \(v_1v_n,v_2v_n\) 均是边，对每个 \(i<n\) ， \(v_i\) 至少连接到一个 \(v_j(j>i)\) ，然后染 \(v_1,v_2\) 为同一种颜色，然后依次染下去。

我们还是倒过来构造序列。因为图不是完全图，所以有顶点 \(x_n\) 的两个邻居 \(x_1,x_2\) 不相邻，然后依次考虑 \(x_{n-1},...,x_3\) ，要使得每个点都与之前的某个点相邻。

假设我们选不了 \(x_{k-1}\) ，那么 \(x_n,x_{n-1},...,x_k\) 只与 \(x_1,x_2\) 之间有边，这意味着删去 \(x_1,x_2\) 会使图不连通。

我们需要分类讨论：

1. \(v_1\) 是割点，我们将 \(v_1\) 去掉后将各连通分支并上 \(\{a\}\) 染色，并将 \(\{a\}\) 的颜色调整至一致，然后合并即可。我们可以关于顶点数归纳，然后用归纳假设。

2. 我们考虑去掉 \(v_1,v_2\) 后得到的某个连通分支 \(H\) ，那么 \(H\) 与 \(v_1,v_2\) 均有边（否则其中的一个就是割点了），然后考虑 \(H\cap \{v_1,v_2\}\) ，加上 \(v_1v_2\) 这条边，最大度数还是不超过 \(\Delta\) （因为 \(v_1,v_2\) 还跟其它的连通分支之间有边），然后对每个 \(H\cup \{v_1,v_2\}\) 染色并调整 \(v_1,v_2\) 的颜色，注意我们连上了 \(v_1v_2\) ，所以它们的颜色一定不同。

如果某个 \(H\cup \{v_1,v_2\}\) 连上 \(v_1v_2\) 是 \(K_{\Delta+1}\) ，根据 \(v_1,v_2\) 的度数不超过 \(\Delta\) ，我们看到它们至多各有一条边连到其它的连通分支，也必须有，否则删除它们不能导致不连通，设为 \(v_1x,v_2y\) 。现在将 \(G\backslash (H\cup \{v_1,v_2\})\) 进行 \(\Delta\) 染色（由于向 \(v_1,v_2\) 中连边，它不可能是 \(K_{\Delta+1}\) ），然后调整 \(v_1,v_2\) 的颜色是某种与 \(x,y\) 均不相同的颜色，再将 \(H\) 染 \(\Delta-1\) 种颜色（注意它们每个点只与 \(H\cup \{v_1,v_2\}\) 连通，由最大度数是 \(\Delta\) ），完成了证明。

我们先展示一些色数比较大的图。

例1

证明：存在无三角形的图，色数大于 \(n\) 。

我们可以轻松归纳完成这个证明。已经构造了色数为 \(n\) 的图 \(G\) ，有 \(m\) 个点，我们再构造 \(n\) 个点，然后让它们拥有 \(n\) 种颜色。比如说颜色 \(1\) ，可以直接找 \(2-n\) 颜色并且不相邻的点，然后让这个点连接这些点。这些点必须存在，因为有一个点染了 \(1\) 色，然后它相邻的点有 \(2-n\) 色，它们两两不相邻，否则去掉 \(1\) 色即可。

然后再构造一个点与这 \(n\) 个点均相邻，它需要第 \(n+1\) 种颜色。

例2

色数为 \(k\) 的子图存在一个子图，任何一个顶点的度数都不小于 \(k-1\) 。

因为度数小于 \(k-2\) 的点直接删去后，不影响整张图的色数。设这个点是 \(v\) ，如果 \(G\backslash \{v\}\) 色数比 \(G\) 少了 \(1\) ，这说明只有 \(v\) 是这一种颜色，但是 \(v\) 只与至多 \(k-2\) 个点相邻，可以把它改成另一种颜色，导致 \(G\) 的色数减少一，这就矛盾。

这样就有很多的推论，比如说，色数为 \(k\) 的图存在一条长为 \(k-1\) 的路径。

例3

\(G\) 有 \(n\) 个顶点，证明： \(\chi(G)\chi(\overline{G})\ge n\)

用 \(c(v),c'(v)\) 表示 \(v\) 在两张图里的颜色，颜色编号为 \(1,2,...,\chi(G)\) 与 \(1,2,...,\chi(\overline{G})\)

我们注意到 \(uv\) 在 \(G,\overline{G}\) 一者中相连，所以 \((c(u),c'(u))\ne (c(v),c'(v))\) ，对任何 \(u,v\) 成立。

而这些有序对都是 \(\{1,2,...,\chi (G)\}\times \{1,2,...,\chi (\overline{G})\}\) 的元素，有 \(n\) 个互不相同的有序对，就给出了结果。