Irreducible graphs in the Grünbaum-Havel 3-colour problem
type: Item
instance of: scholarly article
title: Irreducible graphs in the Grünbaum-Havel 3-colour problem
zbMATH Open document ID: 0859.05041
DOI: 10.1016/0012-365X(95)00114-C
published in: Discrete Mathematics
publication date: 1996-12-08T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 955099
zbMATH Keywords: Grünbaum-Havel problem
zbMATH Keywords: planar graph
zbMATH Keywords: minimal distance
zbMATH Keywords: triangles
zbMATH Keywords: quadrangle
author: Oleg V. Borodin
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Some counterexamples associated with the three-color problem
cites work: Q4273840
cites work: Grötzsch's theorem on 3-colorings
cites work: On a conjecture of B. Grünbaum
cites work: Q3139765
full work available at URL: 0012-365x(95)00114-c
OpenAlex ID: W2001074885
description: scientific article; zbMATH DE number 955099