Note to a problem of T. Gallai and G. A. Dirac
type: Item
instance of: scholarly article
title: Note to a problem of T. Gallai and G. A. Dirac
zbMATH Open document ID: 0593.05030
DOI: 10.1007/BF02579365
author: B. George
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: A graph G is said to be 4-critical if \(\chi (G)=4\) and \(\chi\) (G')\(\leq 3\) for every proper subgraph G' of G. It has been conjectured by G. A. Dirac that every planar 4-critical graph contains vertices of degree 3. \textit{T. Gallai} [Theory Graphs Appl., Proc. Sympos. Smolenice 1963, 43-45 (1964; Zbl 0168.217)] believed that such a graph must contain at least four vertices of degree 3. The author finds a counter-example with 40 vertices each of them of degree 4. His graph is also a counter-example for a conjecture of H. Grötzsch concerning 3-vertex-colorability.
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3952798
zbMATH Keywords: 4-critical graph
zbMATH Keywords: 3-vertex-colorability
MaRDI profile type: Publication
cites work: Q3741635
full work available at URL: https://doi.org/10.1007/bf02579365
OpenAlex ID: W2035948740
description: scientific article; zbMATH DE number 3952798