The Birkhoff Diamond as Double Agent

2018/09/08 by James A. Tilley, Tilley, James A.
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology

paper · pdf · doi:10.48550/arxiv.1809.02807

openalex publication_date 2018/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Despite the existence of a proof of the 4-color theorem, it would seem that there is still more to learn about why any planar graph is 4-colorable. To that end, we take another look at the Birkhoff diamond and discover something new and intriguing: after an extensive search for (rare) Kempe-locked triangulations, we find a Birkhoff diamond subgraph in each one. We offer a heuristic argument as to why that result is not only reasonable but also to be expected and posit that the presence of a Birkhoff diamond is necessary to Kempe-locking. If that conjecture is true, it means that the Birkhoff diamond plays a double role in the matter of 4-colorability, simultaneously working for opposite sides of whether a given planar graph could possibly be a minimum counterexample.

Citations

• The Reducibility of Maps

Related

• The a-graph coloring problem
• Mathematical Proofs of Two Conjectures: The Four Color Problem and The Uniquely 4-colorable Planar Graph
• A note on two conjectures that strengthen the four colour theorem
• A formal proof of the four color theorem
• A renewal approach to prove the Four Color Theorem unplugged, Part III: Diamond routes, canal lines and Σ-adjustments