3-coloring triangle-free planar graphs with a precolored 8-cycle

Abstract

Let G be a planar triangle-free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3-coloring of C does not extend to a proper 3-coloring of the whole graph.

20 pages, 5 figures

References in corpus (2)

• Short proofs of coloring theorems on planar graphs
• 4-critical graphs on surfaces without contractible (<=4)-cycles

Cited by in corpus (5)

• Planar 4-critical graphs with four triangles
• 3-coloring triangle-free planar graphs with a precolored 9-cycle
• The independence ratio of 4-cycle-free planar graphs
• Further Extensions of the Grötzsch Theorem
• Fine structure of 4-critical triangle-free graphs I. Planar graphs with two triangles and 3-colorability of chains