On the Minimum EdgeDensity of 4Critical 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.

published proceedings

  • Journal of Graph Theory

author list (cited authors)

  • Liu, C., & Postle, L.

citation count

  • 1

complete list of authors

  • Liu, Chun‐Hung||Postle, Luke

publication date

  • December 2017

publisher