The a-graph coloring problem: revisiting the 4-color theorem
James A. Tilley · arXiv (Cornell University) · 2015
The existing proofs of the 4-color theorem for planar triangulations do not shed light on why the theorem is true. By examining a related coloring problem that is equivalent to the 4-color problem, we are able to investigate whether there is something fundamental that lies at the heart of the 4-color problem. The equivalent coloring problem applies to a-graphs, near-triangulations of the plane with a face of size 4. We are able to restrict the focus further to a particular family of a-graphs (i) which arise from internally 6-connected triangulations and (ii) for which Kempe exchanges alone cannot solve the new coloring problem. We show that a minimal counterexample to the claim that the a-graph coloring problem can always be solved must belong to this family. A systematic search for members of the family, all of which are believed to be of low order, finds only one among all candidate a-graphs of order not exceeding 20. This sole discovered member is the smallest possible. It is the near-triangulation that results from deleting any edge in the 5-regular icosahedron. It is not an agraph counterexample. We hypothesize that the icosahedral a-graph is the only member of the family and state this conjecture in terms of chromatic numbers applying to the coloring of a-graphs constrained to have a certain type of 2-color internal path between a pair of opposite boundary vertices. Kempe exchanges and the icosahedron are thus seen to have central roles in the 4-color problem.