Основной результат: новая структура планарных графов с ускоренным алгоритмом.

Через полвека после первоначального компьютерного обоснования теоремы четырёх красок группа из шести учёных представила современный вариант доказательства и значительно улучшила производительность. Исследователи продемонстрировали, что раскрасить планарный граф четырьмя цветами можно за почти линейное время O(n log n), в то время как предшествующие лучшие алгоритмы требовали квадратичной временной сложности.

В соответствии с теоремой четырёх красок, любую географическую карту на плоскости можно раскрасить всего четырьмя оттенками так, чтобы смежные регионы отличались по цвету. В контексте теории графов речь идёт о раскраске узлов плоского графа — графа, который можно изобразить без пересечения связей.

Саму теорему не требовалось переделывать или переподтверждать. Первое признанное общемировым сообществом обоснование было разработано Кеннетом Аппелем и Вольфгангом Хакеном в 1976 году с применением вычислительной техники, а его развёрнутое описание вышло в следующем году. В конце 1990-х годов учёные Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас создали более экономное компьютерное обоснование и схему раскраски с временной сложностью O(n²).

Основной вклад новой работы простирается дальше простого повторного подтверждения известного утверждения. Предыдущие подходы искали в плоском графе какую-либо сократимую конструкцию или малый препятствующий контур. Такой участок можно сделать проще, раскрасить сокращённый граф, а затем вернуть отсутствующую часть без нарушения четырёхцветной раскраски.

Текущее исследование показывает, что такие участки в большом плоском графе встречаются многократно. Их число увеличивается в прямой зависимости от объёма графа. Кроме того, сократимые конструкции можно находить практически везде, включая обширные локально «простые» области, где традиционные подходы давали весьма ограниченную информацию.

Это различие критично для работы алгоритма. Классический метод на каждом этапе сокращал проблему лишь на определённое постоянное число узлов, так что последовательность многих сокращений в конечном счёте приводила к квадратичной временной сложности. Современный способ позволяет на одном этапе исключить постоянную часть графа, после этого задача применяется рекурсивно к значительно более компактному объекту. Результатом становится сложность O(n log n).

При обосновании авторы применяют способ перегруппировки нагрузок, связанный с комбинаторной дугообразностью графа. В традиционных обоснованиях локальная положительная дугообразность указывала на место, где должна присутствовать требуемая сократимая конструкция. Новая методология функционирует и в регионах с нулевой дугообразностью, что авторы обозначают как центральный новый компонент работы.

Расходы на повышение скорости были существенными. Обоснование опирается на свыше 8200 D-сократимых конструкций. Для контраста, обоснование Аппеля и Хакена применяло 1482 конструкции, а решение 1996 года сократило перечень до 633. Новому алгоритму нужен намного более полный каталог, так как схема отыскивает не одну подходящую конструкцию, а линейное число независимых участков по всему графу.

Проанализировать тысячи вариантов без компьютерной помощи практически нереально, поэтому значительная часть локального исследования выполняется вычислительной техникой. Создатели опубликовали компьютерный код, 8200 документов с сократимыми конструкциями, 84 принципа перегруппировки нагрузок и инструменты для проверки расчётной доли обоснования. По их расчётам, полная система проверок на системе с 256 ядрами процессора отнимает несколько часов.

Авторы особо отмечают, что исследование не является полностью формализованным компьютерным обоснованием, переписанным в системе автоматической проверки формальных утверждений. Математический анализ ориентирован на восприятие человеком, а обширные переборы передаются программам на языке C++. Специалисты также использовали инструменты машинного обучения для добавочной проверки алгоритма и его реализации, но напрямую указывают, что подобная проверка самостоятельно не гарантирует точность обоснования.

Почти линейная скорость, скорее всего, не будет последней улучшением. В настоящее время главным затруднением остаются цепочки Кемпе, последовательности соседних узлов двух оттенков, переокрашивание которых требуется при возврате удалённых фрагментов графа. Каждая такая операция потенциально затрагивает весь граф. Авторы полагают, что подготовительная обработка информации позволит выполнить все требуемые действия в сумме за O(n) и достичь полностью линейного алгоритма раскраски.

Полученный результат может выйти за границы задачи о географических картах. Обнаруженные плоские участки возникают и в обширных триангуляциях иных фиксированных поверхностей, потому разработанные приёмы потенциально можно адаптировать на более общие вопросы теории графов. Работа уже вошла в повестку конференции FOCS 2026.