On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five Academic Article uri icon

abstract

  • © 2017 Wiley Periodicals, Inc. In a recent seminal work, Kostochka and Yancey proved that |E(G)|≥(5|V(G)|-2/3 for every 4-critical graph G. In this article, we prove that |E(G)|≥(5|V(G)|+2/3 for every 4-critical graph G with girth at least five. When combined with another result of the second author, the improvement on the constant term leads to a corollary that there exist ∈, C > 0 such that |E(G)|≥(5|V(G))|+2)/3 for every 4-critical graph G with girth at least five. Moreover, it provides a unified and shorter proof of both a result of Thomassen and a result of Thomas and Walls without invoking any topological property, where the former proves that every graph with girth five embeddable in the projective plane or torus is 3-colorable, and the latter proves the same for the Klein bottle.

author list (cited authors)

  • Liu, C., & Postle, L.

citation count

  • 0

publication date

  • May 2017

publisher