On the Minimum Edge-Density of 4-Critical Graphs of Girth Five

2014/09/18 by Chun-Hung Liu, Liu, Chun-Hung, Luke Postle +1
Mathematics · #05C #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C

paper · pdf · doi:10.48550/arxiv.1409.5295

17 pages

arxiv created 2014/09/18 · arxiv updated 2014/09/19

Abstract

We prove that if G is a 4-critical graph of girth at least five then |E(G)|>=(5|V(G)|+2)/3. As a corollary, graphs of girth at least five embeddable in the Klein bottle or torus are 3-colorable. These are results of Thomas and Walls, and Thomassen respectively. The proof uses the new potential technique developed by Kostochka and Yancey who proved that 4-critical graphs satisfy: |E(G)|>=(5|V(G)|-2)/3.

Related

• A density bound for triangle-free 4-critical graphs
• Density of 5/2-critical graphs
• On the Minimum Number of Edges in Triangle-Free 5-Critical Graphs
• Three-coloring triangle-free graphs on surfaces III. Graphs of girth\n five
• Solution to a problem of Grünbaum on the edge density of 4-critical planar graphs