任何地图只需四种颜色,就能让相邻国家的颜色总是不同。这在1976年得到了证明。可是,怎样才能真正找出这些颜色呢?
经典工具是肯普链。选两种颜色,取出只涂这两种颜色、彼此相连的一整片国家。把整片区域里的这两种颜色互换:地图的着色依然正确。
问题在于:一次互换可能波及整张地图。之前的最佳纪录在地图变大时需要更多次互换,而每一次都要把整张地图过一遍。
从东京到哥本哈根的六位数学家消除了这项额外开销。他们的算法给n个国家着色所需的时间与n成正比。地图的小块只求解一次,存进表格,之后直接查表即可。作者称这一速度是最优的。
来源:Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










