3-coloring triangle-free planar graphs with a precolored 9-cycle
arXiv:1709.09428 · doi:10.1016/j.ejc.2017.07.010
Abstract
Given a triangle-free planar graph G and a 9-cycle C in G, we characterize situations where a 3-coloring of C does not extend to a proper 3-coloring of G. This extends previous results when C is a cycle of length at most 8.
38 pages, 19 figures
References in corpus (6)
- Planar 4-critical graphs with four triangles
- Short proofs of coloring theorems on planar graphs
- Choosability of planar graphs of girth 5
- 3-coloring triangle-free planar graphs with a precolored 8-cycle
- 4-critical graphs on surfaces without contractible (<=4)-cycles
- Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle