A Victorian Age Proof of the Four Color Theorem

( Доказательство (викторианских времен) теоремы о четырех красках )

Georg A. Gottwald, Ian Melbourne

2009

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

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

Статья полностью:  здесь и здесь.