2013/06/06 by O. V. Borodin, Oleg V. Borodin, Zdeněk Dvořák +5
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar #Planar graph #Planar straight-line graph #acm:05C10 #acm:05C15 #cs.DM #math.CO #msc:05C10 #msc:05C15
paper · pdf · doi:10.1016/j.ejc.2014.03.009
20 pages, 7 figures
arxiv created 2013/06/06 · openalex publication_date 2014/04/23 · arxiv updated 2016/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdos from 1990.