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

2015/09/02 by Yao Tianxing, Tianxing, Yao, Zhou Guofei +1
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.1509.00760

6 pages, 3 figures

arxiv created 2015/09/02 · arxiv updated 2015/09/03

Abstract

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.

Related

• Some New Methods for Constructing 4-critical Planar Graphs
• Solution to a problem of Grünbaum on the edge density of 4-critical planar graphs
• A density bound for triangle-free 4-critical graphs
• On the maximum number of edges in k-critical graphs
• Density of 5/2-critical graphs