Article
3-Choosability of Triangle-Free Planar Graphs with Constraints on 4-Cycles
SIAM Journal on Discrete Mathematics
(2010)
Abstract
A graph is k-choosable if it can be colored whenever every vertex has a list of at least
k available colors. We prove that if a triangle-free planar graph is not 3-choosable, then it contains
a 4-cycle that intersects another 4- or 5-cycle in exactly one edge. This strengthens Thomassen’s
result [C. Thomassen, J. Combin. Theory Ser. B, 64 (1995), pp. 101–107] that every planar graph of
girth at least 5 is 3-choosable. In addition, this implies that every triangle-free planar graph without
6- and 7-cycles is 3-choosable.
Keywords
- planar graph,
- triangle-free graph,
- coloring,
- list coloring,
- choosability
Disciplines
Publication Date
2010
DOI
10.1137/080743020
Publisher Statement
Copyright 2010 Society for Industrial and Applied Mathematics
Citation Information
Zdeněk Dvořák, Bernard Lidicky and Riste Škrekovski. "3-Choosability of Triangle-Free Planar Graphs with Constraints on 4-Cycles" SIAM Journal on Discrete Mathematics Vol. 24 Iss. 3 (2010) p. 934 - 945 Available at: http://works.bepress.com/bernard-lidicky/4/
Creative Commons license
This work is licensed under a Creative Commons CC_BY-NC International License.