Cole–Vishkin 颜色缩减

大颜色携带的绝大多数位，并不参与当前这条边的异色证明。例如颜色 $0={0000}_2$ 与 $8={1000}_2$ 只需用第 $3$ 位即可区分。节点把整串压成“第几位、自己的位值”，标签范围便从 $K$ 缩成约 $2{\log }_{2}K$。难点在于各节点选择的差异位未必相同：我们必须证明这些各自取得的证据仍能形成一个合法染色。

为什么同时更新仍不冲突 ​

固定任意一条定向边 $p(v)\to v$。若两端选择不同的位置，即 $i(p(v))\ne i(v)$，则它们的新颜色分别落在两个不相交的二元集合 $\{2i,2i+1\}$ 中，必然不同。

若两端恰好选择同一位置 $j$，则 $v$ 选择 $j$ 的定义给出

此时两端记录的位值正是这两个不同的比特，所以

这已经覆盖全部情况。论证只看边的两个端点，不需要环的起点，也不例外处理首尾闭合边；因此每轮变换都保持合法染色。反复应用这一不变量，六色阶段的输入仍然合法。

收尾阶段利用的则是另一种局部结构：一个合法颜色类内没有相邻节点。因此同一轮所有颜色为 $q$ 的活动顶点构成独立集，任一活动顶点的两个邻居都保持旧色。两个邻居至多禁用 $\{0,1,2\}$ 中两种颜色，至少剩下一种。活动点的新颜色与两个不变的邻居不同，非活动点之间原有的合法性也未改变。消去 $5$ 后不再产生 $5$，随后同样消去 $4$ 和 $3$，最终只剩 $0,1,2$。

为什么轮数是迭代对数 ​

记 $f(K)=2\lceil {\log }_{2}K\rceil$。对整数 $K>6$，有 $f(K)<K$，而 $f(6)=6$，所以位缩减会到达六色界，却不能靠继续迭代得到三色。若把 $K$ 所在区间写成 $2^{m-1}<K\le 2^m$，则 $f(K)=2m$；从 $m\ge 4$ 起 $2m<2^{m-1}+1\le K$，剩余 $K=7,8$ 可直接检查。

令 $x={\log }_{2}K$。当 $x\ge 16$ 时，取整只造成常数项：

第一步可由 $\lceil x\rceil \le x+1$ 和外层取整误差至多 $1$ 得到；第二步在 $x=16$ 成立，且右边随 $x$ 增长更快。因此每两轮至少取得一次取对数的缩减。降到 $K<2^{16}$ 后，因为整数上界严格下降，只需与输入规模无关的常数轮便到六色以内。

若 ${\log }^{\ast }K$ 表示反复取以 $2$ 为底的对数直到数值不超过 $1$ 所需的次数，位缩减轮数 $T$ 就满足 $T=O({\log }^{\ast }K)$，完整算法需 $T+3$ 轮。当初始 $K=n^{O(1)}$ 时，这可写成 $O({\log }^{\ast }n)$。这里证明的是本算法的上界，尚未给出任何最优性下界。

七点环的五轮完整执行 ​

按给定方向把七点环写成 $v_0\to v_1\to \cdots \to v_6\to v_0$，初始共同上界为 $16$，颜色依次为 $[0,8,10,11,3,7,15]$。包括闭合边在内，每条边的端点都异色。第一轮的逐点计算如下；二进制从低位开始找差异，表中的前驱色均取本轮更新前的值。

第一轮后 $K=8$。第二轮也必须从这一整行旧色重新计算，得到

接下来三轮的轨迹为：

最终闭合边 $v_6{v}_0$ 的颜色为 $2,0$，其余边也均异色。这五轮给出了一份具体三染色；七点奇环本来不能二染，但算法并不需要先判断环的奇偶性。

同一轮必须读取同一份旧状态 ​

如果在数组上从左到右立即覆盖颜色，让后面的点读取前面刚更新的值，执行的就不是上述同步算法。证明中的 $c(p(v))$ 与 $c(v)$ 必须来自同一轮快照，程序可用两个颜色数组或等价的轮次状态来实现。分布式实现中，本轮发送消息也必须在吸收本轮新信息之前由旧状态确定。

只有一致的方向而没有初始合法颜色也不够。若所有节点初始状态完全相同，运行相同确定性程序，各自又看到相同的前驱、后继角色，那么逐轮状态仍然相同，无法得到相邻异色。给定初始合法染色承担了打破这种对称的作用。另一方面，一般有向图可能有多个前驱或更多邻居；任选一个前驱只保护所比较的边，不能把环的证明直接推广到任意度数网络。

这个算法展示了分布式求解与集中式扫描的不同成本：每个节点只看邻居，整个环却同时缩减颜色。最终三色还把节点划成三个互不相邻的集合，可供后续算法分组安排局部操作。这样的安排只保证同组节点不相邻；更远距离的资源冲突仍需另行建模。

设位缩减共有 $T$ 轮，第 $t$ 轮前的上界为 $K_t$，其中 $t=0,\dots ,T-1$。每个节点每轮只向后继发送一个颜色，所以这一阶段恰有 $nT$ 次有向发送；三轮收尾每点每轮向两个邻居发送，共 $6n$ 次。采用固定长度颜色编码时，消息有效载荷总量至多为

最后一项来自收尾的 $6n$ 条、每条至多三位的颜色消息。这不计网络帧、地址和其他实现开销；共同上界及固定调度无需逐条附带发送。轮数、发送次数与位数回答不同问题，不能用 $O({\log }^{\ast }n)$ 轮代替它们全部。

本地处理也并非免费获得常数 CPU 时间。最直接的实现扫描两个长度为 $L$ 的颜色串，需要 $O(L)$ 次位检查；某些机器指令可以加速，但应另报机器字长与运算模型。LOCAL 的一轮只是在通信复杂度上不计这些有限本地工作。对没有已知通信时间界的异步系统，还需要实现合适的模拟或重新证明进展；不能直接把本页轮界解释成其实际运行时间。