Irreducible graphs in the Grünbaum-Havel 3-colour problem
The Grünbaum-Havel problem is: does there exist a constant \(d_0\) such that every planar graph with minimal distance between triangles at least \(d_0\) is 3-colorable? \textit{H. Grötzsch} [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 8, 109-120 (1958; Zbl 0089.39506)] and \textit{B. Grünbaum} [Michigan Math. J. 10, 303-310 (1963; Zbl 0115.40903)] have shown that the following configurations are 3-color reducible: (a) a quadrangle; (b) a pentagon incident with four 3-vertices; and (c) a triangle incident with a 3-vertex (Grötzsch for (a) and (b); Grünbaum for (c)). In the present note, planar graphs are constructed with arbitrarily large minimal distance \(d\) between triangles, having no (b) or (c), and such that the identification of either pair of opposite vertices in any quadrangle gives a decrease in \(d\).
scientific article; zbMATH DE number 955099