Четырёх цветов хватает для любой карты, чтобы соседи всегда различались. Это доказали в 1976 году. Но как на деле найти эти цвета?
Классический инструмент — цепь Кемпе. Возьмите два цвета и весь связный участок стран, окрашенных только в них. Поменяйте их местами во всём участке: карта останется правильно раскрашенной.
Подвох: одна перестановка может прокатиться по всей карте. Прежнему рекорду требовалось тем больше перестановок, чем больше карта. И каждая стоила полного прохода по карте.
Шесть математиков — от Токио до Копенгагена — убрали эти лишние затраты. Их алгоритм раскрашивает n стран за время, пропорциональное n. Небольшие куски карты решаются один раз, сохраняются в таблицах, а затем просто находятся в них. Авторы называют эту скорость оптимальной.
Источник: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










