Solution to a problem of Grünbaum on the edge density of 4-critical planar graphs

2023/11/06 by Dvořák, Zdeněk, Feghali, Carl
#05C10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2311.03132

Abstract

We show that \limsup |E(G)|/|V(G)| = 2.5 over all 4-critical planar graphs G, answering a question of Grünbaum from 1988.

Related

• Constructing a Family of 4-Critical Planar Graphs with High Edge-Density
• On the Minimum Edge-Density of 4-Critical Graphs of Girth Five
• A lower bound on the number of edges in DP-critical graphs. II. Four colors
• A density bound for triangle-free 4-critical graphs
• Density of 5/2-critical graphs