图论03 染色

\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert}

图染色(Coloring)

染色数(Coloring Index)

图的染色分为点染色(vertex coloring)和边染色(edge coloring)

点染色指的是构造映射 $f_k\colon V(G)\mapsto \left{\;1,2,\ldots k\;\right}$，一个合法的染色(proper coloring) 则要求映射满足 $\forall xy\in E(G)\Rightarrow f_k(x)\neq f_k(y)$，记 $k$ 为这个染色方案的染色数(chromatic number)。通常我们只关心最小的染色数，记作 $\chi(G)$

下面讨论的染色都指的是proper coloring

边染色则是类似地构造 $f_k\colon E(G)\mapsto \left{\;1,2,\ldots k\;\right}$，proper的则要求满足 $\forall e_1,e_2\in E(G),\; e_1\cap e_2\neq\varnothing\Rightarrow f_k(e_1)\neq f_k(e_2)$

类似地定义 $\chi\prime (G)$ 为最小的边染色数

关于染色最经典的问题就是著名的“四色定理”的证明。定理的证明非常长…..有兴趣也不会去看的

团(clique)和独立集(independent set)

定义clique number为最大团的大小，记为 $\omega(G)=\max \left{\;H \text{ is a clique}\mid H\subseteq G\;\right}$

定义反团(co-clique)为 $\overline G$ 的团，即 $G$ 的一个独立集。同样定义 co-clique number 为最大独立集的大小，记为 $\alpha(G)$

容易有如下数量关系：

1. $\alpha(G)\cdot \chi(G)\geqslant

   G

   $

2. $n-\alpha(G)\geqslant \chi(G)-1$

3. $\chi(G)\geqslant \omega(G)$

4. $\binom{\chi(G)}{2}\geqslant

   G

   $

1直接由每个独立集染上同一种颜色得到

2的意思是给最大的独立集染上一种颜色，剩下的点用 $\chi(G)-1$ 种颜色染

3的意思是团内部的颜色互不相同

4的意思是同色点之间不能连边，因此至多连 $\binom{\chi(G)}{2}$ 条边

图的色多项式

对图 $G$ 用 $k$ 种颜色染色(我们认为每个节点都不一样)的方案数是关于 $G$ 和 $k$ 的函数，我们不妨记作 $F(G,k)$

只有两种情况：

1. $x,y$ 同色，此时可以把 $x,y$ 收缩成一个点而不改变方案数

2. $x,y$ 异色，此时就是 $F(G,k)$

于是 $F(G,k)+F(G\circ xy,k)=F(G-xy,k)$

染色的贪心算法

关于染色的证明通常通过构造给出一个最小染色数的上界。构造出染色方案的一种常见算法是所谓“贪心算法”，用如下步骤描述：

1. 维护已经染色的点集 $V’$ 和未染色的点集 ${V}’’$

2. 任取 $x\in V’’$，给 $x$ 染上 $N(x)\cap V’$ 中未出现、且最小的颜色

3. 把 $x$ 从 $V’’$ 中删去，再加入 $V’$ 中

4. 若 $V’’=\varnothing$ 则结束算法，否则回到步骤2

容易发现这个算法并不总能给出较好的染色数的界，但仍然给出了一个结果，并且算法的结果与给节点染色的顺序十分相关，因此我们要结合以下引理来改进以下这个算法的效果。

引理一

取图 $G$ 中的任意点 $s$，都存在 $V(G)$ 的一个排列 $v_1,v_2,\ldots v_{n-1}, s$ 使得 $\forall 1\leqslant i< n$ 都有 $\exists j>i,\;v_j\in N(v_i)$。

为了好记我把这个叫排列引理

只需要构造出这样的序列即可。我们取 $G$ 中以 $s$ 为根的生成树 $T$，每次从 $T$ 中取出叶子，这样就能保证每个点在被放进序列时都有至少一个邻居在它的后面，且根是一定放在最后的。

这样结合贪心染色可以得到 $\chi(G)\leqslant \max\left{\;\text{deg}(s)+1,\Delta(G-s)\;\right}$

引理二

若非完全图 $G$ 满足 $\delta(G)\geqslant 3$ 且 $\kappa(G)\geqslant 2$，那么 $\exists x,y\in V(G)$ 使得 $\exists v\in V(G),\; xv,yv\in E(G)\text{ and } xy\not\in E(G)$

并且有 $G-\left{\;x,y\;\right}$ 仍然连通。

取 $G$ 的一个极小分隔集 $T$，则 $|T|=\kappa(G)\geqslant 2$。记 $C$ 为 $G-T$ 形成的连通分支的集合，那么有 $\forall x\in T$，$\forall c_i\in C,\; N_G(x)\cap c_i\neq\varnothing$

于是取 $v\in T$，令 $x,y$ 分别取自不同的分支，那么必然有 $xy\not\in E(G)\text{ and } xv,yv\in E(G)$。

并且删去 $x,y$ 后它们所属的分支仍然连通($\kappa(c_x)\geqslant 2\text { and }\kappa(c_y)\geqslant 2$)，$\left{\;c_x,c_y,x\;\right}$ 仍然连通($\text{deg}(x)\geqslant 3$)，得到一个矛盾

染色数的平凡上界

任意图 $G$ 都有 $\chi(G)\leqslant \Delta (G)+1$。

这个上界直接由贪心算法得到。

Brooks Theorem

$G$ 是连通图，那么 $\chi(G)=\Delta(G) + [G \text{ is complete or an odd cycle}]$，其中 $[x]=1$ 当且仅当表达式 $x$ 为真。

首先 $G$ 是完全图的情况很显然，奇数圈的情况也很简单，反证法就可以说明不存在方案了。

然后 $\Delta(G)\leqslant 2$ 的情况也很好讨论，就是一个圈，因此下面讨论的都是 $\Delta(G)\geqslant3$ 的图。

1. $\kappa(G)=1$，即 $G$ 存在一个割点 $x$，则 $G=G_1\cup G_2$，其中 $G_1\cap G_2=\left{\;x\;\right}$。那么我们对 $G_1$、$G_2$ 分别染色，由归纳假设得到他们方案的并就是 $G$ 的一个合法染色方案，因此 $\chi(G)=\max\left{\;\chi(G_1),\chi(G_2)\;\right}\leqslant\max\left{\;\Delta(G_1),\Delta(G_2)\;\right}\leqslant \Delta(G)$ 得证。

2. $\kappa(G) \geqslant 2$，且存在 $x\in V(G)$ 使得 $\text{deg}(x)<\Delta(G)$，则根据引理一构造 $x$ 在最后的序列并贪心染色，这样就有 $\chi(G)\leqslant\Delta(G)$

3. $\kappa(G)\geqslant 2$，且 $\forall x\in V(G)$ 都有 $\text{deg}(x)=\Delta(G)=\delta(G)$，则根据引理二存在 $x,y,v\in V(G)$ 使得 $xv,yv\in E(G)$ 且 $xy\not\in E(G)$。我们把 $x,y$ 染上同种颜色，根据引理一把 $v$ 放在序列末尾，这样就可以贪心地染出 $\chi(G)\leqslant \Delta(G)$ 了。

图的定向(orientation)

图定向的严格定义是构造映射 $f\colon E(G)\mapsto V(G)\times V(G)$，简单地说就是给无向边定方向

我们称有向无环图(Directed Acyclic Graph) 为DAG，DAG有许多优秀的性质

DAG的染色算法

对于给定的有向无环图 $G$，我们给出如下染色算法步骤：

1. 我们需要维护一个映射 $g\colon V(G)\mapsto \mathbb N^+$，$g(x)$ 表示以节点 $x$ 为终点的最长路长度。

2. 找到 $x\in V(G)$ 使得 $x$ 的入度为0，在 $N_G(x)$ 中找到已经走过的点中 $g(v)$ 的最大值，令 $g(x)=g(v)+1$

3. 删去 $x$，标记 $x$ 已经走过了。若还有未经过的点则返回步骤2

细心的朋友们很快就可以发现这是一个拓扑排序上的计数。很显然 $g$ 下任意相邻节点的函数值都不相等。于是我们caim：找到的映射 $g$ 就是一个染色方案。

不妨记 $p(G)$ 表示DAG图 $G$ 中最长路的长度，那么有 $\chi(G)\leqslant p(G)$

复杂度是可以做到 $\Theta(n+m)$ 的

利用图定向给出染色数的紧界

不妨设 $H$ 是图 $G$ 的任意一个定向，$K$ 是 $H$ 极大的不含有向圈的子图，那么有：

$\chi(G)\leqslant p(K)$，并且存在一个定向使得它们恰好相等

这个结论是很强的。不等号的部分在DAG的染色中已经给出，我们只需要考虑 $E(G)\backslash E(K)$ 中的边加入后会不会产生相同颜色的相邻节点就好了。由 $K$ 的定义可知 $\forall uv\in (E(G)\backslash E(K))$，有 $K+uv$ 会产生一个有向圈，即 $K$ 中存在一条 $v-u$ 有向路，这保证了 $g(v)\neq g(u)$

下面证明存在一个定向的极大无圈子图 $K$ 使得 $p(K)=\chi(G)$。我们只需要证明 $p(K)\leqslant\chi(G)$

首先用 $\chi(G)$ 给 $G$ 染色，然后对 $G$ 定向：若 $uv\in E(G)$ 有 $c(u)<c(v)$，则构造定向 $f(uv)=(u,v)$，否则 $f(uv)=(v,u)$

即我们规定边只能从小颜色连向大颜色。这样 $K$ 中路的长度至多为 $\chi(G)$，也就是 $p(K)\leqslant \chi(G)$

这个定向实际上是在枚举所有贪心算法的操作序列，也就是说存在至少一种操作的顺序使得我们trivial的贪心算法能够摸到 $\chi(G)$ 的门槛。

平面图的五色定理

四色定理太难勒，这里有一个比较好玩的弱化版本——任意平面图(plane graph)/可平面图(planar graph)是5-可着色(colorable)的

引理一

推论1：平均度为 $\frac{2||G||}{|G|}=\frac{6|G|-12}{|G|}<6$，因此 $\exists x\in V(G)$ 使得 $\text{deg}(x)\leqslant 5$

推论2：极大可平面图删去任意点仍然是可平面图，因此 $\forall x\in V(G)$ 都有 $\text{deg}(x)\geqslant 3$

引理二

极大可平面图中任意点的邻居导出一个圈

只需要找到一个平面画法，删去这个点，观察这个点所在的区域的边界即可。

可平面图不好直接做，因此我们向 $G$ 加边直至 $G$ 成为极大可平面。只需证明新图 $G’$ 仍然是 5-可染色即可。

讨论：

1. $\text{deg}(x)<5$，则由贪心算法可知加上 $x$ 也不需要超过5种颜色。

2. $\text{deg}(x)=5$，则 $x$ 有恰好 $5$ 个邻居
3. 若5个邻居中存在两个颜色相同，则染上 $x$ 也只需要至多5种颜色
4. 若5个邻居互不相同，则需要特殊讨论。

现在来看2.2的情况。根据引理二我们得到5个点共圈，不妨按顺序记为 $v_1, v_2,\ldots v_5$，其颜色分别为 $c_1,c_2\ldots c_5$ 那么我们做如下操作：

1. 把 $v_1$ 的颜色换成 $c_3$

2. 把与 $v_1$ 距离为1的点中，颜色为 $c_3$ 的点的颜色换成 $c_1$

3. 把距离为2的点做同样操作….

4. 直到不存在可以更改颜色的点剩下。

若流程终止了，则我们通过switch得到了一个染色方案，而 $c(v_1)\neq c(v_3)$，即5个邻居只用了4种颜色，那么 $G$ 就是5-可染色的了。

若最后一直换到了 $v_3$，即存在一条 $v_1-v_3$ 路，使得路上的节点颜色交替为 $c_1,c_3,c_1,c_3\ldots c_3$，那么此次交换无效(没有达到预期的目的)

再类似地考虑 $v_2,v_4$，若成功则证明完毕，否则存在一条 $v_2-v_4$ 颜色交替路

注意到 $G$ 是平面图，因此不存在这样两次都失败的情况(why？)，即 $v_2-v_4$ 和 $v_1-v_3$ 必然相交。因此证毕。

二分图的染色

这个非常sb，二分图嘛，黑白染色黑白染色，$\chi(G)=2$

还有边染色的部分，先去吃饭…

回来填坑了

图的边染色

具体定义见上面

首先给出一个简单的关于边染色的界的结论：

$\forall G$, $\chi’(G)\geqslant \Delta(G)$

这个界的证明非常简单，只需要找到度数最大的节点，给它的边染上颜色就好了

二分图的边染色

若 $G$ 是二分图，则 $\chi’(G)=\Delta(G)$

首先有 $\chi’(G)\geqslant\Delta(G)$，因此只需要证明 $\chi’(G)\leqslant\Delta(G)$ 即可

我们对 $||G||$ 归纳，设当 $||G||<n$ 时命题成立，则取 $xy\in E(G)$，$\chi’(G-xy)\leqslant\Delta(G-xy)\leqslant\Delta(G)$

考虑加入 $xy$ 这条边，那么$\text{deg}{G-xy}(x)\leqslant\Delta(G),\text{deg}{G-xy}(y)\leqslant\Delta(G)$。不妨记 $M(x)$ 为 $x$ 相邻的边中没被用过的颜色，则分两种情况讨论：

1. $M(x)\cap M(y)\neq\varnothing$，则给 $xy$ 染上 $M(x)\cap M(y)$ 中的任意一种颜色，$\chi’(G)\leqslant\Delta(G)$

2. $M(x)\cap M(y)=\varnothing$，则 $\exists a\in M(x), b\in M(y)$ 使得 $a\not\in M(y),b\not\in M(x)$。类比点的染色，我们尝试通过交换来让出一种颜色。即令 $x$ 邻边中染上 $b$ 颜色的边换成 $a$ 颜色，并沿着这条边走向一个邻居；再令这个邻居染上 $a$ 颜色的邻边换成 $b$ 颜色….. 直至走到一个不用换颜色的节点，则停止

   • 我们claim这样的走法一定能换成功，即使走回了起点。原因在于这是一个二分图，所有的圈都是偶圈，而我们交替地走着 $a,b,a,b,\ldots$ 的边，因此最后必然可以走出一条路(这样就直接交换颜色)或一个圈(这样就相当于轮换了一圈的颜色)

于是就证完了

一个任意图的更强的界

事实上 $\forall G$ 都有 $\Delta(G)\leqslant\chi’(G)\leqslant\Delta(G)+1$

这个证明有点麻烦，咕了吧（