任何地图的四种颜色，都能在线性时间内找到

任何画在平面上的地图都可以用四种颜色着色，使相邻国家的颜色永远不同。弗朗西斯·格斯里（Francis Guthrie）在1852年提出了这一猜想；阿佩尔（Appel）和哈肯（Haken）在1976年证明了它。但这个定理只说明四种颜色的着色方案存在。对于给定的地图，怎样把它找出来？“没有简单的答案，”东京大学的Yuta Inoue和来自日本、加拿大、斯洛文尼亚和丹麦的五位同事写道。这个问题错综复杂，曾引出许多被提出的“反例”。

点、线和三角形

每个国家变成一个点，即顶点；每段共享边界变成一条线，即边：地图就变成了一个平面图，可以画成没有线相互交叉的样子。给它着色，就是给每个顶点分配四种颜色之一，并且每条边两端的颜色不同。把顶点数记为n。只需处理三角剖分就够了，即每个面都是三角形的图：边越多，着色只会越难。

肯普互换

基本操作可以追溯到A. B. 肯普（A. B. Kempe）1879年的一篇论文。把四种颜色两两配对，比如红配蓝、绿配黄。肯普链是由一对颜色中的两种颜色构成的一组相连顶点。沿整条链互换这两种颜色，着色仍然有效。

取一个有四个邻居的顶点v，邻居按环绕顺序记为v0到v3，先给其余部分着色。如果邻居只用了三种或更少的颜色，v就取那种空出来的颜色。如果它们用了全部四种，就沿着从v0出发、由v0和v2的颜色构成的链走。如果这条链没有到达v2，就把它互换：v0取得v2的颜色，为v空出一种颜色。如果它确实到达了v2，就改为互换v1所在的、由v1和v3的颜色构成的链，使v1取得v3的颜色。

总能修复的小块

四色定理的证明依赖于可约构形：一些可以先挖掉、等其余部分着色后再放回去的小图案。如果它们的环——紧挨在它们周围的那些顶点——的颜色不合适，在外部做有限次改进性的肯普变换总能修好：对这里使用的图案而言最多25次，这些图案的环最多有18个顶点。

一个可约构形（左；每个数字表示该顶点在完整地图中必须拥有的邻居数），以及由其环R补全的同一图案（右）。——图1，Inoue等（2026），arXiv:2610.39753。

1997年，罗伯逊（Robertson）、桑德斯（Sanders）、西摩（Seymour）和托马斯（Thomas）展示了如何用这种方法着色，一次处理一个图案。每一轮把图缩小几个顶点，代价是把整个图过一遍，因此所需时间是二次的：地图大一倍，时间就长四倍。

在之前的一篇论文（FOCS’26）中，同样这六位作者证明了：每个三角剖分都含有与n成正比数量的、互不接触的可约构形，取自一份包含8202个图案的清单——或者含有同样多的、两侧都有顶点的短环，这些短环同样有用。他们一次性移除所有图案，给其余部分着色，再一起修复所有的环。一次随机的肯普变换能帮到某个给定的环，前提是它选对了颜色配对（三分之一的机会），并且在每条触及该环的链上都抛对了硬币（每条二分之一的机会）。这样的链最多有18条，所以机会至少是3 × 2¹⁸分之一，即786432分之一：很小，但是固定的。因此所需轮数只按log n增长，大致是n能被对半分的次数。但一次变换可能牵涉图中固定比例的部分：每次都要完整过一遍，总共是n log n。

用查表代替遍历

新论文保留了log n次变换，但让每一次都更便宜。经过与n成正比时间的准备后，每次变换平均只需约n / log n步就能找到并执行。于是log n次变换加起来所需的时间与n成正比——即线性时间——作者称这一上界是最优的。

诀窍是“四个俄罗斯人方法”（Method of Four Russians）。一个能装进½ log n位编码的子问题——也就是写下n所需二进制位数的一半——最多只有√n种可能的版本，因此可以预先算出所有答案并存进一张表。所假定的计算机的内存字长约为log n位，一步就能读出任何存储的答案。

图被一次又一次地切分成边界很短的嵌套区域。最小的区域约含log n个顶点，连同颜色在内正好装进一个编码。对每个区域，用一个小的摘要图记录哪些边界顶点共享同一条肯普链。这样，一次变换就以一串“互换”或“保持”的比特向下传递，而在每个小区域中，一次查表就能更新所有颜色。

用四种颜色着色的图的一部分。灰色区域是一个区域R；粗黑边属于红–蓝和绿–黄两对颜色的肯普链。——图2，Inoue等（2026），arXiv:2610.39753。

同一区域的摘要：每个蓝色团块代表一段肯普链，它的连线表明它连接了哪些边界顶点。——图3，Inoue等（2026），arXiv:2610.39753。

不掷骰子也能选择

借助随机选择，这种方法已经能在平均线性时间内给地图着色。在不损失速度的前提下去掉骰子，是“迄今为止最具挑战性的部分”。只要迄今为止的每个决定都对某个环有利，就称这个环是“存活”的。如果触及它的u条尚未决定的链都交给抛硬币，它存活的概率就是1/2^u；对所有存活的环求和，这些数值给出预期存活的环的数量。决定一条链，会使每个想要这一选择的环的对应项加倍，其余环的项归零。算法总是选择不让这个和下降的选项，这样到最后，得到帮助的环至少和随机选择平均能帮到的一样多。

一个上界，而不是一块秒表

论文没有报告任何实现，也没有给出运行时间，“与n成正比”中隐藏的常数也没有给出。这些常数很大：对8202个图案中的每一个，算法都要存储其环的每种着色需要多少次改进性变换——“海量的常数级信息”。在附录中，作者还修正了他们所依据的2013年一种嵌套区域构造中的“一个小错误”。一个1852年的猜想，如今有了一套着色程序，其代价的增长不会快于它所着色的地图。