图论5-Coloring
图论5-Coloring
Vertex Coloring
为图的每个顶点分配某种颜色，称一种着色是正确的，如果没有两个相邻的顶点着色相同；
一个独立集(independent set)是指内部没有任意两个点相邻的点集；
因此，在一个正确的着色中，位于不同独立集的点集可以被不同颜色着色；
一个$k$-点着色的无环图可以被划分为$k$个独立集$V_1\cup V_2\cup \cdots\cup V_k$;
图的一个$k$-点着色是用$k$个颜色对其顶点进行着色；若图是一个$k$-点可着色的，如果图有一个正确的$k$-点着色方式；
图$G$的色数(chromatic number)$\chi (G)$等于最小的使得$G$是$k$-点着色的整数；
称图$G$是$k$-色(k-chromatic)图，如果$\chi(G)=k$;
确定一个图是否是3-可着色的是一个NPC问题，对于平面图，计算机已经证明四色定理：对于任何平面图$G$均有$\chi(G)\le 4$;
对于给定的图确定色数是一个NP问题，但是色数有一个平凡上界$\chi(G)\le n$;
Theorem
$$
\chi(K_n)=n\
\chi(C_n)=2+(n% 2)\
$$
值得一提的是，Petersen图的色数为3；
Theorem
$$
\chi(G)\le \Delta(G)+1
$$
Proof:以下贪心算法是一种 正确的着色方案，这说明我们找到了色数的一个上界；
假设第$i$个颜色记作$C_i$,列举图$G$的顶点$v_1,v_2,\cdots.v_n$;
- 为$v_1$分配颜色$C_1$;
- 对于状态$i+1$,假定$v_1,v_2,\cdots,v_i$已经着色，分配$v_{i+1}$颜色$C_j$,$j$为$v_{i+1}$相邻顶点尚未使用的颜色最小下标；
等号在奇圈和完全图上成立；
Five-color Theorem
简单平面图是5-可着色的；
proof：对$|V(G)|$归纳，若$|V(G)|\le 5$,结论平凡，假设$|V(G)|\le n$成立，考虑度数最小的点$v$，一定有$d(v)\le 5$,由归纳假设，对于除去点$v$的图存在$5-$着色方案，若$d(v)\le 4$，则$v$的邻居一定为$v$留出一个颜色；
考虑$d(v)=5$,记邻居顺时针方向为$v_1,v_2,v_3,v_4,v_5$,若这5个点只用了4个颜色，剩下的颜色留给$v$即可；若这5个点颜色各不相同，假设$v_1$染1色，$v_2$染2色，将$v_3$改染1色，$c$染1色的邻居改染2色，依次类推；
若这样的操作不i能持续下去，一定出现如下情况的子图
由平面性，$v_2,v_4$不会有这样的通路，对$v_2,v_4$进行上述操作即可；
进一步，我们有四色定理(Four-color theorem, Appel and Haken):任意简单平面图都是4-可着色的，即$\chi(G)\le 4,\forall G\text{is planar graph}$;
经过对偶图变换可以得知，世界地图可以用4种颜色进行染色；
Brooks Theorem
对于非奇圈的非完全的简单连通图$G$,有$\chi(G)\le \Delta(G)$;
proof：若存在度数小于$\Delta(G)$的顶点$v$，我们需要精心安排顶点的顺序，使得每个顶点在染色时，排在它前面并与之相邻的顶点数不超过$\Delta-1$,以$v$为根的图$G$生成树的后序遍历序列满足条件，因为除$v$外，其余顶点在这棵生成树的父亲一定位于这个点序列的后面；
假设图$G$是$\Delta$正则的；进一步假设$\Delta(G)\ge 3$；
若$G$有割点，取图$G$的割点$v_n$，以及两个连通分量$C_1,C_2$,取$v_1\in C_1,v_2\in C_2$,且$v_1,v_2$均是$v_n$的邻居；
对于$G-{v_n}$的任意连通分量$G_i$，可以对$H_i=G_i\cup{v_n}$进行$k$着色，对这样方案下每个$H_i$的着色顺序进行置换，使得他们在$v_n$的颜色一致；
进一步假设$\kappa(G)=2$，即$G$是2连通的，断言图$G$存在三个顶点$v_1,v_2,v_n$,使得$G-{v_1.v_2}$连通，且
$$
v_1v_n\in E(G),v_2v_n\in E(G),v_1v_2\notin E(G)
$$
先将$v_1,v_2$染成同色，对于$G-{v_1,v_2}$,考虑令$v=v_n$,贪心地为其他点染色后，最后染$v_n$时，由于有两个邻点$v_1,v_2$同色，因此一定留有一种颜色；
下证明断言：若$G$是3连通的，因为$G$是正则且不完全的，故选取距离为2的两点$v_1,v_2$和公共邻点$v_n$即可；
若$G$不是3连通的，但是是2连通的，由于$G$没有割点，每个叶块均有$v_n$的相邻顶点，由于$\Delta \ge 3$，因此可以选取两个不直接相邻的叶块中与$v_n$的邻点$v_1,v_2$；
Map Coloring
在地图着色问题中，不考虑地图之间的桥梁；
定义地图(map)为一个3连通的平面图；
称一个地图是$k$-面可着色的，如果它的面可以被$k$个颜色着色且有公共边相邻的面颜色不同；
Theorem
地图$G$是2-面可着色当且仅当$G$是欧拉图；
proof：对于每个顶点，一定有偶数个围绕它的面(两种颜色的面个数相同)，意味着其度为偶数，$G$为欧拉图
如果$G$为欧拉图，则选取任意一个面染为红色，对于其他面，到$F$的曲线穿过偶数条边染为红色，奇数条边染为蓝色，这样的染法是良定义的，因为每个顶点有偶数度
Edge Coloring
图的一个$k$-边着色是用$k$个颜色对其边进行着色；
一个正确的边着色满足任意两个相关联的边颜色不同；
若图是一个$k$-边可着色的，如果图有一个正确的$k$-边着色方式；
不相关联的独立边集合称作一个匹配(matching)，更确切地说，在图$G$中的一个匹配$M$是一组互相没有公共顶点无环边集合，称顶点$v$被匹配$M$浸润的(saturated),若$v$关联$M$中的一条边，否则称为未浸润的(unsaturated);
一个正确的$k$-边可着色可以认为对边集进行划分
$$
E=E_1\cup E_2\cup\cdots E_k
$$
其中$E_i$是一个匹配，每个匹配分配相同的颜色；
边色数(edge chromatic number)$\chi’(G)$定义为最小正整数$k$使得$G$为$k$-边可着色的；
一个平凡下界为$\chi’(G)\ge \Delta(G)$;
Theorem
$$
\chi’(K_n)=n-1+(n%2)
$$
对于奇数$n$，任何匹配至多拥有$\frac{n-1}{2}$条边，但是$K_n$有$\frac{n(n-1)}{2}$条边，因此$\chi’(G)\ge n$；
给出$n$-边着色的构造：边界用$n$种颜色染色，对角线的颜色和与之平行的边颜色相同；
对于偶数$n$，我们给出$n-1$-边着色的构造：
取出点$v$,先为$K_{n-1}$子图的用上述方案染色，每个顶点的关联边共$n-2$种颜色，留下一个颜色与$v$相连的边染色即可；
Theorem(Vizing)
对于有限图$G$，两点间最大连边数为$\mu$，则$G$为$\Delta(G)+\mu$-可染色的；
对于简单图来说，$\chi’(G)=\Delta\rm{or}\Delta + 1$
Theorem(Konig)
对于二部图$G$，$\chi’(G)=\Delta(G)$
proof:对边数归纳，假设在较小的边数成立，考虑删除一条边$vw$，子图最大度不超过$\Delta(G)$,对子图$\Delta(G)$边染色，在子图中，$d(v)< \Delta(G),d(w)<\Delta(G)$,因此这样的边染色方案中，$v,w$关联的边至少剩余一种颜色没有使用，设为$c_v,c_w$，若$c_v=c_w$,将$vw$染为该色即可；否则，考虑关联$v$的染$c_w$色的边$vu_1$,依次用$c_v,c_w$色边增广它，得到增广路径不会经过$w$点(因为没有奇圈)，反转增广路径的颜色后将$uw$染为$c_w$色即为最终的染色方案；
Chromatic Polynomial
对于简单图$G$，定义色数函数$P_G(k)$为将$G$顶点用$k$种颜色染色，相邻顶点不同色的方案$(f:V(G)\to [k])$数;
Theorem
对于简单图$G$，有
$$
P_G(k)=P_{G-e}(k)-P_{G\cdot e}(k)
$$
proof:考虑删除一条边后的子图之间的关系，$G-e$可以看作边顶点没有限制关系，$G/e$可以看作边顶点必须同色；
显然$P_G(k)$是一个$|V|$次多项式，满足如下性质
- 系数正负交替；
- $x^{|V|-1}$的系数是$-|E|$；
- 常数项为0；