## 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 language | English (US) |
---|---|

Pages (from-to) | 387-405 |

Number of pages | 19 |

Journal | Journal of Graph Theory |

Volume | 86 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2017 |

## All Science Journal Classification (ASJC) codes

- Geometry and Topology

## Keywords

- coloring
- critical graphs
- girth five