The -graph coloring problem

详细信息    查看全文

• 作者：J.A. Tilley ^{jimtilley@optonline.net}
• 关键词：4-color problem ; Minimal counterexample ; Kempe exchange ; Equivalence class ; Birkhoff diamond
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：304-317
• 全文大小：806 K
• 卷排序：217

文摘

No proof of the 4-color conjecture reveals why it is true; the goal has not been to go beyond proving the conjecture. The standard approach involves constructing an unavoidable finite set of reducible configurations to demonstrate that a minimal counterexample cannot exist. We study the 4-color problem from a different perspective. Instead of planar triangulations, we consider near-triangulations of the plane with a face of size 4; we call any such graph an aa-graph. We state an aa-graph coloring problem equivalent to the 4-color problem and then derive a coloring condition that a minimal aa-graph counterexample must satisfy, expressing it in terms of equivalence classes under Kempe exchanges. Through a systematic search, we discover a family of aa-graphs that satisfy the coloring condition, the fundamental member of which has order 12 and includes the Birkhoff diamond as a subgraph. Higher-order members include a string of Birkhoff diamonds. However, no member has an applicable parent triangulation that is internally 6-connected, a requirement for a minimal counterexample. Our research suggests strongly that the coloring and connectivity conditions for a minimal counterexample are incompatible; infinitely many aa-graphs meet one condition or the other, but we find none that meets both.