Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes\n of 4-critical graphs

2014/04/25 by Zdenĕk Dvořák, Dvorak, Zdenek, Daniel Král͏̌ +3
Computer Science · Mathematics · #05C10 (Secondary) #05C15 (Primary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1404.6356

openalex publication_date 2014/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a 4-critical graph with t triangles, embedded in a surface of genus\ng. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We\nprove that the sum of lengths of (>=5)-faces of G is at most linear in g+t+c-1.\n

Related

• Three-coloring triangle-free graphs on surfaces III. Graphs of girth\n five
• 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
• Irreducible 4-critical triangle-free toroidal graphs