Irreducible graphs in the Grünbaum-Havel 3-colour problem (Q1126208)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Irreducible graphs in the Grünbaum-Havel 3-colour problem |
scientific article |
Statements
Irreducible graphs in the Grünbaum-Havel 3-colour problem (English)
0 references
8 December 1996
0 references
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\).
0 references
Grünbaum-Havel problem
0 references
planar graph
0 references
minimal distance
0 references
triangles
0 references
quadrangle
0 references