图的着色
点着色¶
（讨论的是无环无向图）
对无向图顶点着色，且相邻顶点不能同色。若 G 是 k - 可着色的，但不是 (k-1) - 可着色的，则称 k 是 G 的色数，记为 \chi'(G) 。
对任意图 G ，有 \chi(G) \leq \Delta(G) + 1 ，其中 \Delta(G) 为最大度。
Brooks 定理¶
设连通图不是完全图也不是奇圈，则 \chi(G) \leq \Delta(G) 。
边着色¶
对无向图的边着色，要求相邻的边涂不同种颜色。若 G 是 k - 边可着色的，但不是 (k-1) - 边可着色的，则称 k 是 G 的边色数，记为 \chi'(G) 。
Vizing 定理¶
设 G 是简单图，则 \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1
若 G 是二部图，则 \chi'(G)=\Delta(G)
当 n 为奇数（ n \neq 1 ）时， \chi'(K_n)=n ; 当 n 为偶数时， \chi'(K_n)=n-1
二分图 Vizing 定理的构造性证明¶
按照顺序在二分图中加边。
我们在尝试加入边 (x,y) 的时候，我们尝试寻找对于 x 和 y 的编号最小的尚未被使用过的颜色，假设分别为 lx 和 ly 。
如果 lx=ly 此时我们可以直接将这条边的颜色设置为 lx 。
否则假设 lx<ly , 我们可以尝试将节点 y 连出去的颜色为 lx 的边的颜色修改为 ly 。
修改的过程可以被近似的看成是一条从 y 出发，依次经过颜色为 lx,ly,\cdots 的边的有限唯一增广路。
因为增广路有限所以我们可以将增广路上所有的边反色，即原来颜色为 lx 的修改为 ly ，原来颜色为 ly 的修改为 lx 。
根据二分图的性质，节点 x 不可能为增广路节点，否则与最小未使用颜色为 lx 矛盾。
所以我们可以在增广之后直接将连接 x 和 y 的边的颜色设为 lx 。
总构造时间复杂度为 O(nm) 。
一道很不简单的例题 uoj 444 二分图
本题为笔者于 2018 年命制的集训队第一轮作业题。
首先我们可以发现答案下界为度数不为 k 倍数的点的个数。
下界的构造方法是对二分图进行拆点。
若 degree \bmod k \neq 0 ,我们将其拆为 degree/k 个度数为 k 的节点和一个度数为 degree \bmod k 的节点 。
若 degree \bmod k = 0 ,我们将其拆为 degree/k 个度数为 k 的节点。
拆出来的点在原图中的意义相同，也就是说，在满足度数限制的情况下，一条边端点可以连接任意一个拆出来的点。
根据 Vizing 定理，我们显然可以构造出该图的一种 k 染色方案。
删边部分由于和 Vizing 定理关系不大这里不再展开。
有兴趣的读者可以自行阅读笔者当时写的题解。
色多项式¶
f(G,k) 表示 G 的不同 k 着色方式的总数。
f(K_n, k) = k(k-1)\cdots(k-n+1)
f(N_n, k) = k^n
在无向无环图 G 中，
- e=(v_i, v_j) \notin E(G) ，则 f(G, k) = f(G \cup (v_i, v_j), k)+f(G\backslash(v_i, v_j), k)
- e=(v_i, v_j) \in E(G) ，则 f(G,k)=f(G-e,k)-f(G\backslash e,k)
定理：设 V_1 是 G 的点割集，且 G[V_1] 是 G 的 |V_1| 阶完全子图， G-V_1 有 p(p \geq 2) 个连通分支，则：
f(G,k)=\frac{\Pi_{i=1}^{p}{(f(H_i, k))}}{f(G[V_1], k)^{p-1}}
其中 H_i=G[V_1 \cup V(G_i)]
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用