ИИ ОПРОВЕРГ ГИПОТЕЗУ О РАСКРАСКАХ ИЗ 1990-Х
Возьмём сеть из точек, соединённых линиями, — граф. Тотальная раскраска присваивает цвет каждой точке и каждой линии по трём правилам: две соседние точки различаются, две линии, сходящиеся в точке, различаются, и линия отличается от обеих своих концевых точек. Наименьшее подходящее число цветов называется тотальным хроматическим числом и обозначается χ″(G).
Теперь усложним задачу. Дадим каждой точке и каждой линии собственный список разрешённых цветов, все списки одного размера k, и потребуем правильную раскраску, выбранную из этих списков. Наименьшее k, которое работает при любых списках, — это списочное тотальное хроматическое число χ″ℓ(G). Оно никогда не может быть меньше χ″(G): если все списки одинаковы, мы возвращаемся к обычной задаче.
Гипотеза конца 1990-х
Три группы — Бородин, Косточка и Вудалл; Юван, Мохар и Шкрековски; Хилтон и Джонсон — независимо друг от друга предположили в конце 1990-х, что личные списки никогда ничего не стоят:
χ″ℓ(G) = χ″(G) для любого графа (даже с несколькими линиями между двумя точками).
Это гипотеза о списочной тотальной раскраске. Факты говорили в её пользу: она верна для графов, в которых ни у одной точки нет больше двух линий, и было известно, что любому графу ровно с тремя линиями на точку (кубическому графу) требуется не более 5 цветов из списков.
Контрпример
Джонатан Ноэль из Университета Виктории в Канаде теперь предъявил кубический граф из 20 точек, у которого χ″ = 4, но χ″ℓ = 5. Гипотеза неверна.
Построение компактно. Возьмём четыре копии маленького графа K₂,₃: две «личные» точки, каждая соединена с одними и теми же тремя «терминальными» точками. Затем соединим каждую пару копий ровно одной «перекрёстной» линией между терминалами. В итоге у каждой точки по три линии.
Граф G с тотальной раскраской всего в четыре цвета, показанные фигурами и стилями линий. — Рисунок 1, Noel (2026), arXiv:2609.38417.
В обычной игре хватает четырёх цветов: цвет 4 достаётся всем личным точкам и всем перекрёстным линиям, которые никогда не соприкасаются друг с другом, а с остальным справляются небольшая таблица и циклическое правило.
Списки, которым невозможно угодить
Ловушка использует цвета от 1 до 5. Каждая точка и линия блока i получает список «все цвета, кроме i»; перекрёстные линии получают тщательно подобранные списки без 5 или без i + 2. Дальше доказательство разворачивается как короткий детектив:
- Лемма: в любой 4-раскраске K₂,₃ две личные точки должны быть одного цвета.
- Значит, у каждого блока i есть пара цветов {i, sᵢ}, и каждая перекрёстная линия между двумя блоками должна использовать цвет, общий для обеих пар.
- Небольшой подсчёт показывает, что некоторый цвет t должен входить во все четыре пары.
- Для каждого возможного t одна конкретная перекрёстная линия обнаруживает, что этого цвета нет в её списке. Противоречие.
Назначение списков: каждая точка и линия может использовать все цвета от 1 до 5, кроме указанного. Ни одна тотальная раскраска не может уважать эти списки. — Рисунок 2, Noel (2026), arXiv:2609.38417.
Найдено машиной, проверено математиком
Статья необычно откровенна насчёт своего происхождения. 24 сентября 2026 года Ноэль попросил ChatGPT 6 Astra Ultra опровергнуть гипотезу, и модель выдала контрпример «при незначительном участии автора». Он проверил рассуждения и переписал текст на основе черновиков, сгенерированных моделью; модель также помогла с вычиткой, предложила ссылки и нарисовала рисунки. «Автор несёт полную ответственность за корректность», — заканчивается заявление. Статья — препринт, но доказательство достаточно короткое, чтобы любой терпеливый читатель мог его проверить.
Разрыв в один цвет — или больше?
Личные списки могут стоить одного лишнего цвета. А могут ли больше? Разрыв в три цвета опроверг бы и хорошо изученную родственную гипотезу — гипотезу о списочной рёберной раскраске, поскольку χ″ℓ ≤ χ′ℓ + 2 и χ″ ≥ χ′. Ноэль завершает статью открытым вопросом, который контрпример ИИ оставляет в силе: верно ли, что χ″ℓ(G) ≤ χ″(G) + 1 для любого графа?