Article
On Choosability with Separation of Planar Graphs with Forbidden Cycles
Journal of Graph Theory
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
3-1-2016
DOI
10.1002/jgt.21875
Abstract
We study choosability with separation which is a constrained version of list coloring of graphs. A (k; d)-list assignment L of a graph G is a function that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at most d colors. A graph G is (k; d)-choosable if there exists an L-coloring of G for every (k; d)-list assignment L. This concept is also known as choosability with separation. We prove that planar graphs without 4-cycles are (3; 1)-choosable and that planar graphs without 5-cycles and 6-cycles are (3; 1)-choosable. In addition, we give an alternative and slightly stronger proof that triangle-free planar graphs are (3; 1)-choosable.
Copyright Owner
Wiley Periodicals, Inc.
Copyright Date
2015
Language
en
File Format
application/pdf
Citation Information
Ilkyoo Choi, Bernard Lidicky and Derrick Stolee. "On Choosability with Separation of Planar Graphs with Forbidden Cycles" Journal of Graph Theory Vol. 81 Iss. 3 (2016) p. 283 - 306 Available at: http://works.bepress.com/bernard-lidicky/38/
This is the peer-reviewed version of the following article: Choi, Ilkyoo, Bernard Lidický, and Derrick Stolee. "On choosability with separation of planar graphs with forbidden cycles." Journal of Graph Theory 81, no. 3 (2016): 283-306, which has been published in final form at doi: 10.1002/jgt.21875. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving. Posted with permission.