Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk

2013/02/08 by Dvorak, Zdenek, Kral, Daniel, Thomas, Robin
#05C10 (Secondary) #05C15 (Primary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1302.2158

Abstract

Let G be a plane graph of girth at least five. We show that if there exists a 3-coloring phi of a cycle C of G that does not extend to a 3-coloring of G, then G has a subgraph H on O(|C|) vertices that also has no 3-coloring extending phi. This is asymptotically best possible and improves a previous bound of Thomassen. In the next paper of the series we will use this result and the attendant theory to prove a generalization to graphs on surfaces with several precolored cycles.

Related

• Three-coloring triangle-free graphs on surfaces III. Graphs of girth\n five
• 3 List Coloring Graphs of Girth at least Five on Surfaces
• Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes\n of 4-critical graphs
• Three-coloring triangle-free graphs without long forbidden paths
• Three coloring via triangle counting