Skip to main content
profile image
Selected Works of Bernard Lidický
Article
Planar 4-critical graphs with four triangles
European Journal of Combinatorics (2014)
  • Oleg V. Borodin, Sobolev Institute of Mathematics
  • Zdeněk Dvořák, Computer Science Institute of Charles University
  • Alexandr V. Kostochka, University of Illinois at Urbana–Champaign
  • Bernard Lidicky, University of Illinois at Urbana–Champaign
  • Matthew Yancey, University of Illinois at Urbana–Champaign
Download Find in your library
Abstract
By the Grünbaum–Aksenov Theorem (extending Grötzsch’s Theorem) every planar graph with at most three triangles is -colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdős from 1990.
Disciplines
Publication Date
October, 2014
DOI
10.1016/j.ejc.2014.03.009
Publisher Statement
This is a manuscript of an article from Borodin, Oleg V., Zdeněk Dvořák, Alexandr V. Kostochka, Bernard Lidický, and Matthew Yancey. "Planar 4-critical graphs with four triangles." European Journal of Combinatorics 41 (2014): 138-151. DOI: 10.1016/j.ejc.2014.03.009. Copyright 2014 Elsevier Ltd. Posted with permission.
Citation Information
Oleg V. Borodin, Zdeněk Dvořák, Alexandr V. Kostochka, Bernard Lidicky, et al.. "Planar 4-critical graphs with four triangles" European Journal of Combinatorics Vol. 41 (2014) p. 138 - 151
Available at: http://works.bepress.com/bernard-lidicky/14/