前言
在港中文的暑研快结束的时候，由于大家快没事干了，一个本地的同学就给我分享了一个简单但不失趣味的图论定理，于是记在这里。
记号与约定
除特殊约定外，下文中所有变量均取正整数。
对于图 \(G\)，称 \(V_G, E_G\) 为其点集和边集。在上下文明了的情况下，下标 \(G\) 会被忽略。
为了保证记号统一，用 \((u,v)\) 描述一条边，在有向图情境下其表示一条从 \(u\) 到 \(v\) 的边，在无向图情境下其表示一条连接 \(u\) 和 \(v\) 的边。
定义记号 \([k] = \{1,2,\cdots,k\} = [1,k] \cap \mathbb{Z}\)。
定义函数 \(b\) 满足
- \(\forall k \in \mathbb{Z}^+, b(k) = \binom{k}{\lfloor \frac{k}{2} \rfloor}\)；
- \(\forall k \in \mathbb{Z}^+, t \in (0,1), b(k+t) = tb(k+1) + (1-t)b(k)\)。
注意到 \(b\) 的定义域和值域都是 \([1,+\infty)\)。
（注：对于函数 \(b\)，实际上只有整数上的值是比较有意义的，非整数上的值只是为了让 \(b^{-1}(k)\) 对于任意整数 \(k\) 都有定义且规避一些边界问题。）
相关定义
可 \(k\) 着色 (\(k\)-colorable)：当我们可以给图 \(G\)（无论其是有向还是无向）的所有节点设定 \([k]\) 中的一个整数，使得每条边连接的两个节点设定的整数不同，则称图 \(G\) 可 \(k\) 着色。形式化地，\(G\) 可 \(k\) 着色当且仅当 \(\exists f: V \to [k]\), s.t. \(\forall (u,v) \in E, f(u) \neq f(v)\)。
\(a\) v.s. \(b\) 着色问题：这个问题要求区分可 \(a\) 着色的图和不可 \(b\) 着色的图。具体地，给出一个图 \(G\)，保证其要么是可 \(a\) 着色的要么是不可 \(b\) 着色的，这个问题要求确定给出的图是否是 \(a\) 着色的。在参考文献中这个问题是用 Promise CSP 的方式描述的，为了最小化专业名词我们忽略掉这个部分。
线图 (Line graph)：对于一个有向图 \(G\)，按如下方式定义其线图 \(\partial G\)：
- \(V_{\partial G} = E_G\)；
- \(E_{\partial G} = \{((u,v),(v,w)) \mid (u,v) , (v,w) \in V_{\partial G}\}\)。直观地说，\(E_{\partial G}\) 描述了 \(G\) 中长度为 \(2\) 的路径。
对于一个无向图 \(G\)，按如下方式定义其线图 \(\partial G\)：将 \(G\) 转化为双向的有向图，求一次对应图的线图，然后将有向边改为无向边。按如下方式定义其二阶线图 \(\partial \partial G\)（注：有向图的二阶线图就是对线图再求一次线图）：将 \(G\) 转化为双向的有向图，求其线图的线图，然后将有向边改为无向边。
也就是说，对于无向图 \(G\)，我们总是把它当成双向有向图来看并作用线图操作，最终再将其变换回无向图。
注意如上方式定义的线图与常见的无向图线图不同。
定理 —— 原图与线图的着色关系
定理 1（有向图版本）：对于任意有向图 \(G\)，
- 若 \(\partial G\) 可 \(k\) 着色，则 \(G\) 可 \(2^k\) 着色。
- 若 \(G\) 可 \(b(k)\) 着色，则 \(\partial G\) 可 \(k\) 着色。
定理 2（无向图版本）：对于任意无向图 \(G\)，\(G\) 可 \(b(k)\) 着色当且仅当 \(\partial G\) 可 \(k\) 着色。
定理 3：对于任意可 \(4\) 着色图 \(G\)，\(\partial \partial G\) 可 \(3\) 着色。
想知道定理有啥用可以先跳过证明。
定理证明
定理 1 (1.) 证明：
注意到对 \(\partial G\) 的点着色就是对 \(G\) 的边着色，因此 \(\partial G\) 可 \(k\) 着色意味着存在 \(G\) 的一个 \(k\)-边着色使得任意长度为 2 的路径包含两条不同颜色的边。
固定一个 \(k\)-边着色 \(c: E_g \to [k]\)，对于 \(G\) 中的节点 \(v\)，设 \(S_v = \{c_{(u,v)} \mid (u,v) \in E_G\}\)，即原图中所有进入 \(v\) 的边的颜色集合。注意到 \(S_v \subseteq [k]\)，所以总共有 \(2^k\) 种不同的 \(S_v\)。所以如果 \(\forall (u,v) \in E_G\) 都有 \(S_u \neq S_v\)，那么我们“用 \(S_v\) 给 \(v\) 着色”，就可以得到一个合法的 \(2^k\) 着色。
注意到 \(\forall (u,v) \in E_G\)，\(c_{(u,v)} \in S_v\)，而若 \(\exists x \in V_G\)，\(c_{(x,u)} = c_{(u,v)}\)，那么就存在一个长度为 2 的路径包含两条同色的边，不满足 \(c\) 是一个 \(\partial G\) 的 \(k\) 着色的条件。因此 \(c_{(u,v)} \not\in S_u\)，从而 \(S_u \neq S_v\)。\(\square\)
定理 1 (2.) 证明：注意到 \(b(k) = \binom{k}{\lfloor \frac{k}{2} \rfloor}\) 描述了从 \([k]\) 中选出 \(\lfloor \frac{k}{2} \rfloor\) 个元素的方案，因此与 1 (1.) 的证明类似，我们可以将 “用 \(b(k)\) 种颜色着色” 等价为 “用 \([k]\) 的大小为 \(\lfloor \frac{k}{2} \rfloor\) 的子集着色”。
定义 \(S_u (u \in V_G)\) 为对应的集合着色。\(\forall (u,v) \in E_G\)，由于 \(|S_u| = |S_v|\) 但 \(S_u \neq S_v\)，\(S_v \backslash S_u \neq \varnothing\)。
我们任意选择 \(S_v \backslash S_u\) 的一个元素作为 \((u,v)\) 的颜色 \(c_{(u,v)}\)。这样我们得到了一个 \(k\)-边着色，且 \(\forall (x,u),(u,v) \in E_G\)，由于 \(c_{(x,u)} \in S_u\) 而 \(c_{(u,v)} \not\in S_u\)，\(c_{(x,u)} \neq c_{(u,v)}\)，因此这个着色对应了 \(\partial G\) 的一个 \(k\) 着色。
定理 2 证明：
必要性同 定理 1 (2.) 一致，只需证明充分性。延续 定理 1 (1.) 的证明思路，但此时一条无向边对应双向的有向边，因此 \(S_u \backslash S_v\) 和 \(S_v \backslash S_u\) 都不是空集。因此 \((S_u,S_v)\) 对应一条边的一个必要条件是 \(S_u \not\subseteq S_v\) 且 \(S_v \not\subseteq S_u\)。
平凡的做法是将不同的 \(S_u\) 对应到不同的整数。但注意到，如果一个集族 \(\mathcal{F}\) 满足 \(\forall S_1, S_2 \in \mathcal{F}, S_1 \subseteq S_2\) 或 \(S_2 \subseteq S_1\)，那么 \(\mathcal{F}\) 里的集合可以对应到同一种颜色，因为图上没有任何一条边对应的两个集合都在 \(\mathcal{F}\) 里。
根据 Sperner's Theorem，我们可以选出 \(b(k)\) 个集族 \(\mathcal{F}_i\)，保证集族间两两无交、并为全集，且每个集族均满足上述条件，而 \(b(k)\) 是最小的可能值。这样我们就得到了原图的 \(b(k)\) 着色。
（注：对于 CP 选手来说，这一步更好的理解方法是，注意到 \(\mathcal{F}\) 是原图的一条反链，也就是补图的链，然后由于补图上两个集合间连边当且仅当其中一个包含另一个，这是一个偏序，所以用 Dilworth 定理，最少集族数量对应最小链覆盖，也就是最长反链。然后一个经典结论是补图的最长反链就是所有大小为 \(\lfloor \frac{k}{2} \rfloor\) 的集合。）
定理 3 证明：
首先考虑 \(\partial \partial G\) 和 \(G\) 的关系：\(V_{\partial \partial G} = E_{\partial G}\) 描述了 \(G\) 中长度为 \(2\) 的路径，而由于 \(V_{\partial G}=E_G\)，因此 \(\partial \partial G\) 里两条长度为 2 的路径有边，当且仅当第一条路径的第二条边和第二条路径的第一条边是同一条。为了方便，我们用 \((u,v,w) = ((u,v),(v,w))\) 描述 \(V_{\partial \partial G}\) 中的元素，在这样的符号下 \((u,v,w)\) 到 \((v,w,x)\) 在 \(\partial \partial G\) 中有边。
我们先对 \(K_4\) 证明该定理，此时对 \((u,v,w)\) 的限制只有 \(u \neq v, v \neq w\)。注意到我们直接设 \(c((u,v,w)) = v\) 就得到了一个 4 染色，考虑如何将多的颜色删掉。当 \(v=4\) 的时候，\(u,w \le 3\)，因此 \((u,v,w)\) 的所有前驱 \((x,u,v)\) 都会着颜色 \(u\)，而所有后继 \((v,w,y)\) 都会着颜色 \(w\)，所以我们给 \((u,v,w)\) 着 \([3] \backslash \{u,w\}\) 里的某个颜色就得到一个合法的 3 染色。
对于一般图来说，它的一个四染色可以看作是对 \(K_4\) 的“嵌入”（学术叫法应该是同态），因此自然的做法是把这个嵌入和上述构造复合在一起。也就是说，不妨假设 \(g\) 是原图的四染色，那么
\[c(u,v,w) = \begin{cases} g(v), & g(v) \le 3, \\ \text{任意元素取自} [3] \backslash \{g(u), g(w)\}, & g(v) = 4. \end{cases} \]就是一个合法的 \(\partial \partial G\) 的 3 染色。
定理应用
根据以上三个定理，我们可以得到推论：若存在 \(x \ge 3\) 使得任意 \(y \ge x\) 均有 \(x\) v.s. \(y\) 着色问题是 NP-Hard 的，那么 \(\forall 3 \le x < y\)，\(x\) v.s. \(y\) 着色问题是 NP-Hard 的。
证明：不妨假设给定的图是无向图。我们分两步证明这个推论：
- 第一步：若存在 \(x \ge 3\) 使得任意 \(y \ge x\) 均有 \(x\) v.s. \(y\) 着色问题是 NP-Hard 的，那么 \(\forall y > 3\)，\(3\) v.s. \(y\) 着色问题是 NP-Hard 的。
- 注意到 \(b^{-1}(k)\) 对于 \(k \ge 1\) 是良定义的。考虑对 \(x\) 归纳证明。
- 当 \(x=3\) 时显然成立。
- 当 \(x=4\) 时，我们可以将 \(4\) v.s. \(y\) 着色问题归约到 \(3\) v.s. \(\lfloor b^{-1}(b^{-1}(y)) \rfloor\) 着色问题：
- 如果 \(G\) 可以 \(4\) 染色，那么根据定理 3 \(\partial \partial G\) 可以三染色，否则根据定理 2 \(\partial \partial G\) 不可 \(\lfloor b^{-1}(b^{-1}(y)) \rfloor\) 染色。
- 容易检验 \(\lfloor b^{-1}(b^{-1}(y)) \rfloor\) 包含所有大于等于 \(4\) 的整数。
- 当 \(x \ge 5\) 时，我们可以将 \(x\) v.s. \(y\) 着色问题归约到 \(\lceil b^{-1}(x) \rceil\) v.s. \(\lfloor b^{-1}(y) \rfloor\) 着色问题：
- 根据定理 2，\(G\) 可以 \(x\) 染色则 \(\partial G\) 可以 \(\lceil b^{-1}(x) \rceil\) 染色，\(G\) 不可以 \(y\) 染色则 \(\partial G\) 可以 \(\lfloor b^{-1}(y) \rfloor\) 染色。
- 容易检验 \(x \ge 5\) 时 \(\lceil b^{-1}(x) \rceil \le x\) 且 \(\lfloor b^{-1}(y) \rfloor\) 覆盖了所有大于 \(\lceil b^{-1}(x) \rceil\) 的整数，然后使用归纳假设。
- 注意到 \(b^{-1}(k)\) 对于 \(k \ge 1\) 是良定义的。考虑对 \(x\) 归纳证明。
- 第二步：若 \(\forall y > 3\)，\(3\) v.s. \(y\) 着色问题是 NP-Hard 的，那么 \(\forall 3 \le x < y\)，\(x\) v.s. \(y\) 着色问题是 NP-Hard 的。
- 这一步是相对简单的，因为我们可以给出一个较为显然的将 \(3\) v.s. \(y\) 着色问题归约到 \(x\) v.s. \(y\) 着色问题的方法：用 \(x\) v.s. \(y\) 的算法判断给出的图是否可 \(x\) 染色，如果不可 \(x\) 染色，那么其不可 \(y\) 染色；否则其可以 \(3\) 染色。
这样对于 \(x\) v.s. \(y\) 染色问题的 hardness，我们只需要固定一个 \(x\) 就行了，不过 \(3\) v.s. 任意常数的 hardness 似乎现在还是 open 的。
参考文献
- C.C Harner, R.C Entringer, “Arc Colorings of Digraphs.” Journal of Combinatorial Theory, Series B, Volume 13, Issue 3, 1972, Pages 219-225.
- Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing, vol. 52, no. 1, Feb. 2023, pp. 38–79. Crossref, https://doi.org/10.1137/20m1378223.