图论与组合 / 习题/考试 / 作业 / 5

1. 下界

任取圆上连续 $k+1$ 个点, 两两相邻, 构成团, 故 $\chi(G_{n,k})\ge k+1$. 若存在 $(k+1)$-着色, 则每串连续 $k+1$ 个点必须颜色各异, 绕圆一圈只能周期性出现 $1,2,\dots,k+1$. 因此只有当 $k+1\mid n$ 时才能完成 $(k+1)$-着色, 且此时用模 $k+1$ 的颜色 $c(i)\equiv i\pmod{k+1}$ 即得 $\chi(G_{n,k})=k+1$.

2. 上界

写 $n=q(k+1)+r$ ($1\le r\le k$) . 当 $n\ge k(k+1)$ 时有 $q\ge k\ge r$. 先把 $q-r$ 个整段用模式 $1,2,\dots,k+1$ 着色；余下 $r(k+2)$ 个顶点用 $1,2,\dots,k+1,k+2$ 的模式着色, 共重复 $r$ 次. 边界处最多与前后 $k$ 个邻点冲突, 而颜色有 $k+2$ 种, 故可行. 结合上一步得 $\chi(G_{n,k})=k+2$ (当 $k+1\nmid n$).

3. 若 $n=k(k+1)-1$ 仍想用 $k+2$ 色, 则某一色至少出现 $k$ 次, 其相邻两次出现的最小间距 $<k+1$. 但距离 $\le k$ 的两点相邻, 矛盾. 故 $\chi(G_{k(k+1)-1,k})>k+2$.

取 $G$ 的一个最优着色 $f$, 颜色集合为 $\{1,2,\dots,\chi(G)\}$. 我们按颜色从小到大排顶点:

先排所有 $f$-色为 $1$ 的, 再排所有 $f$-色为 $2$ 的, $\ldots$, 最后排所有 $f$-色为 $\chi(G)$ 的. 记此顺序为

对 $i$ 做归纳, 证明贪心算法给 $v_i$ 分配的颜色 $\le f(v_i)$.

1. $i=1$ 时显然成立.

2. 假设 $j<i$ 的都已成立, 即贪心给每个 $v_j$ 都用 $\le f(v_j)$ 的颜色. 考虑 $v_i$. 和 $v_i$ 同色的那些 $v_j$ (即 $f(v_j)=f(v_i)$), 在 $G$ 中不与 $v_i$ 邻接. 所以这些同色点不会与 $v_i$ 冲突.

于是, $v_i$ 的已着色邻点中, 其颜色最多只会出现在 $\{1,2,\dots,f(v_i)-1\}$ 里, 不可能出现到 $f(v_i)$. 因此贪心在给 $v_i$ 上色时最多只会用到 $f(v_i)$.

综上, 贪心在该顺序上最多用颜色 $\chi(G)$, 而 $\chi(G)$ 又是理论最少色数, 所以可以做到用 $\chi(G)$ 色.

在所有 $n$ 顶点、无 $K_{r+1}$ 的图中取一张边数极大的 $G$. 对任意不相邻的 $u,v$, 把 $v$ 的邻集改成 $N(u)$. 这不会产生 $K_{r+1}$, 也不减少边数；反复上述操作可得一张完全多部图, 并且其每个部内为独立集、任意两部间完备相连. 若其部数为 $s>r$, 则包含 $K_{r+1}$, 与“极大且无 $K_{r+1}$”矛盾；故极值图必为完全 $r$ 部图 $K_{n_1,\dots,n_r}$, 其中 $\sum_{i=1}^r n_i=n$.

于是

$\sum_{i=1}^r n_i^2\ge r\bigl(\frac{n}{r}\bigr)^2=\frac{n^2}{r}$, 等号当且仅当 $n_1=\cdots=n_r=n/r$. 代回得到

当 $G$ 取为各部尽量均衡的完全 $r$ 部图时取等号.

设 $G$ 为不含 $K_{r+1}$ 的极大边数图. 对任意不相邻顶点 $u,v$, 把 $v$ 的邻集改为 $N(u)$. 这不会产生 $K_{r+1}$, 且不减 边数. 对称化重复直到所有非邻点对都可对称, 得到 $G^\ast$. 标准结论: 若某一步出现 $e$ 严格增加, 则 $G$ 不是极大；因此极大时每一步都 保持等号, 从而 $G$ 已在每一步的等号条件下不变. 等号条件强制 所有非邻点属于同一独立集, 所有不同独立集之间完全相连, 于是 $G$ 已是完全 $r$ 部图 $G=K_{n_1,\ldots,n_r},\ \sum n_i=n.$

完全 $r$ 部图的边数

$\sum n_i^2\ge r\bigl(\frac{n}{r}\bigr)^2,$ 且当且仅当 $n_1,\dots,n_r$ 两两相差不超过 $1$ 时取等. 因此若存在 $n_i\ge n_j+2$, 把一个顶点从较大的部移到较小的部会使 $\sum n_i^2$ 下降、$e(G)$ 上升, 矛盾. 故极值部大小必为 $\lfloor n/r\rfloor$ 或 $\lceil n/r\rceil$, 并且这是唯一的等号情形.