Toward a New Proof of the Four Coloring Theorem

Abstract

John Clairmont

A heuristic algorithm is described for four coloring planar graphs. The algorithm is based on the principle of breaking a problem into components and solving them one at a time. The algorithm uses gen- eralized alternating chains of the most general kind, for instance they can have branches and self-inter- sections. Alternating chains are found which, after completing each major iteration of the algorithm, a certain property is preserved. This property ensures that a successive alternating chain will be easy to find.

Specifically, the property ensures that the branches of an alternating chain cannot conflict with each other, and a branch cannot conflict with itself. This algorithm solves one set of problems, but the solution has its own set of problems. However, I think these can be easily resolved, leading to a new and simple proof of the Four-Color Theorem.

PDF