基于贪心着色算法衍生顺序的图着色颜色数合理性验证

咱们先明确下贪心着色的规则：给定图 $G=(V,E)$ 和顶点的一个排序 $v_1, \ldots, v_n$，贪心着色算法是这么给顶点分配颜色的：

• 首先给第一个顶点 $v_1$ 分配颜色 $0$；
• 对于后续的每个顶点 $v_i$（$i≠1$），它的颜色是满足「前面已经着色的邻居都没用到这个颜色」的最小非负整数，也就是：
  $$
  c(v_i) = \min_{z \in \mathbb{N}_0} \text{ s.t. 没有 } v_i \text{ 的前置邻居（排序中在它前面的邻居）使用颜色 } z
  $$

接下来是我关心的核心问题：假设我们用某个任意顶点顺序跑贪心着色，得到了一个用 $t$ 种颜色的着色结果，把每个颜色对应的顶点集合记为 $V_i$（$V_i$ 是所有被染成颜色 $i$ 的顶点）。现在如果我们把顶点顺序改成「先放 $V_0$ 的所有顶点（顺序任意），接着放 $V_1$ 的，直到 $V_{t-1}$」，再跑一次贪心着色，会用到多少种颜色？

我琢磨着，这次贪心着色最多用 $t$ 种颜色，甚至可能更少，给你捋捋我的思路：

基础观察：颜色类的独立性 #

首先得明确，每个 $V_i$ 都是独立集——同一个颜色类里的顶点之间没有边，这是贪心着色的基本性质，毕竟如果有边的话，后面那个顶点肯定会被分配不同的颜色。

最好情况：颜色数远小于 $t$ #

当我们按 $V_0, V_1, \ldots, V_{t-1}$ 的顺序跑贪心时：

• $V_0$ 的所有顶点都会被染成颜色 $0$，因为它们之间没边，前面也没有其他顶点；
• 对于 $V_i$（$i>0$），如果它的所有顶点都和 $V_0 \cup \ldots \cup V_{i-1}$ 里的顶点没边，那这些顶点也都能被染成颜色 $0$——不过这里有个矛盾：如果真的是这样，那原来的贪心着色应该也能把这些顶点染成颜色 $0$，根本不会用到 $t$ 种颜色，所以这种极端情况实际上不存在。

那更合理的最好情况是：每个 $V_i$（$i>0$）只和前面某一个颜色类 $V_j$（$j<i$）有边相连。比如：

• $V_0$ 染成颜色 $0$；
• $V_1$ 因为和 $V_0$ 有边，所以染成颜色 $1$；
• $V_2$ 只和 $V_0$ 或者只和 $V_1$ 有边，那就能选没被用的那个颜色（比如只和 $V_0$ 相连就用颜色 $1$，只和 $V_1$ 相连就用颜色 $0$）；
• 以此类推，后面所有的 $V_i$ 都能在颜色 $0$ 或 $1$ 里选到可用的，最终整个图只需要2种颜色，远小于原来的 $t$。这说明确实存在贪心着色用更少颜色的情况。

最坏情况：颜色数等于 $t$ #

如果每个 $V_i$（$i>0$）都和前面所有的颜色类 $V_0, V_1, \ldots, V_{i-1}$ 有至少一条边相连，那情况就不一样了：

• $V_0$ 染成颜色 $0$；
• $V_1$ 因为和 $V_0$ 有边，所以用颜色 $1$；
• $V_2$ 和 $V_0$、$V_1$ 都有边，所以只能用颜色 $2$；
• ……
• 最后 $V_{t-1}$ 和前面所有 $t-1$ 个颜色类都有边，只能用颜色 $t-1$。
  这种情况下，贪心着色就会用到恰好 $t$ 种颜色。

结论确认 #

综合上面的分析，按这种颜色类顺序跑贪心着色，用到的颜色数最多是 $t$，而且确实可能比 $t$ 少。这个结论是正确的吗？

备注：内容来源于stack exchange，提问作者lafinur