Constructing a Family of 4-Critical Planar Graphs with High Edge-Density

Original · EN

A graph G=(V,E) is a k-critical graph if G is not (k -1)-colorable but G-e is (k-1)-colorable for every e∈ E(G). In this paper, we construct a family of 4-critical planar graphs with n vertices and 7n-13/3 edges. As a consequence, this improved the bound for the maximum edge density obtained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4-critical planar graph.