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

Chun Hung Liu, Luke Postle

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)387-405
Number of pages19
JournalJournal of Graph Theory
Volume86
Issue number4
DOIs
StatePublished - Dec 2017

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • coloring
  • critical graphs
  • girth five

Fingerprint Dive into the research topics of 'On the Minimum Edge-Density of 4-Critical Graphs of Girth Five'. Together they form a unique fingerprint.

Cite this