Premium
On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five
Author(s) -
Liu ChunHung,
Postle Luke
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22133
Subject(s) - mathematics , corollary , combinatorics , klein bottle , graph , odd graph , girth (graph theory) , torus , discrete mathematics , chordal graph , 1 planar graph , geometry
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 3 + ε ) | V ( G ) | + c 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.