Note to a problem of T. Gallai and G. A. Dirac (Q1076035)

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.