Article
3-coloring triangle-free planar graphs with a precolored 9-cycle
European Journal of Combinatorics
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
2-1-2018
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.
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Ltd.
Copyright Date
2017
Language
en
File Format
application/pdf
Citation Information
Ilkyoo Choi, Jan Ekstein, Premysl Holub and Bernard Lidicky. "3-coloring triangle-free planar graphs with a precolored 9-cycle" European Journal of Combinatorics Vol. 68 (2018) p. 38 - 65 Available at: http://works.bepress.com/bernard-lidicky/41/
This is a manuscript of an article published as Choi, Ilkyoo, Jan Ekstein, Přemysl Holub, and Bernard Lidický. "3-coloring triangle-free planar graphs with a precolored 9-cycle." 68 European Journal of Combinatorics (2018): 38-65. doi: 10.1016/j.ejc.2017.07.010. Posted with permission.