Constructing a Family of 4‐Critical Planar Graphs with High Edge Density
Tianxing Yao, Guofei Zhou · Journal of Graph Theory · 2017
Abstract A graph is a k‐critical graph if G is not ‐colorable but every proper subgraph of G is ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.