zbMATH — the first resource for mathematics

The $$a$$-graph coloring problem. (English) Zbl 1358.05119
Summary: 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 $$a$$-graph. We state an $$a$$-graph coloring problem equivalent to the 4-color problem and then derive a coloring condition that a minimal $$a$$-graph counterexample must satisfy, expressing it in terms of equivalence classes under Kempe exchanges. Through a systematic search, we discover a family of $$a$$-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 $$a$$-graphs meet one condition or the other, but we find none that meets both.

MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
References:
 [1] Appel, K.; Haken, W., Every planar map is four colorable, part i: discharging, Illinois J. Math., 21, 3, 429-490, (1977) · Zbl 0387.05009 [2] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable, part i: reducibility, Illinois J. Math., 21, 3, 491-567, (1977) · Zbl 0387.05010 [3] Birkhoff, G., The reducibility of maps, Amer. J. Math, 70, 114-128, (1913) · JFM 44.0568.01 [4] Fisk, S., Geometric coloring theory, Adv. Math., 24, 3, 298-340, (1977) · Zbl 0358.05023 [5] Las Verngas, M.; Meyniel, H., Kempe classes and the hadwiger conjecture, J. Combin. Theory Ser. B, 31, 1, 95-104, (1981) · Zbl 0471.05028 [6] Meyniel, H., LES 5-colorations d’un graphe planaire forment une class de commutation unique, J. Combin. Theory Ser. B, 24, 3, 251-257, (1978) · Zbl 0385.05035 [7] Mohar, B., Kempe equivalence of colorings, (Graph Theory in Paris, (2007), Birkhauser Basel) · Zbl 1115.05035 [8] Robertson, N.; Sanders, P.; Seymour, P.; Thomas, R., The four-color theorem, J. Combin. Theory Ser. B, 70, 1, 2-44, (1997) · Zbl 0883.05056 [9] J. Steinberger, An unavoidable set of d-reducible configurations. arXiv:0905.0043v3 [math.CO], 2009. · Zbl 1221.05165 [10] Stromquist, W., Some aspects of the four color problem, (1975), Harvard University, (Ph.D. thesis) [11] E. Weisstein, Errera graph. MathWorld — A Wolfram Web Resource, http://mathworld.wolfram.com/ErreraGraph.html. [12] E. Weisstein, Heawood four-color graph. MathWorld — A Wolfram Web Resource, http://mathworld.wolfram.com/HeawoodFour-ColorGraph.html. [13] E. Weisstein, Kittell graph. MathWorld — A Wolfram Web Resource, http://mathworld.wolfram.com/KittellGraph.html. [14] Wilson, R., Four colors suffice, (2002), Princeton University Press · Zbl 1030.05041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.