Three-coloring triangle-free graphs on surfaces III. Graphs of girth\n five

2014/02/19 by Zdenĕk Dvořák, Dvořák, Zdeněk, Daniel Král͏̌ +3
Computer Science · Mathematics · #05C15 (Primary) 05C10 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1402.4710

openalex publication_date 2014/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the size of a 4-critical graph of girth at least five is bounded\nby a linear function of its genus. This strengthens the previous bound on the\nsize of such graphs given by Thomassen. It also serves as the basic case for\nthe description of the structure of 4-critical triangle-free graphs embedded in\na fixed surface, presented in a future paper of this series.\n

Related

• Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes\n of 4-critical graphs
• Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk
• 3 List Coloring Graphs of Girth at least Five on Surfaces
• A density bound for triangle-free 4-critical graphs
• On the Minimum Edge-Density of 4-Critical Graphs of Girth Five