Skip to main content
Article
(4, 2)-Choosability of Planar Graphs with Forbidden Structures
Graphs and Combinatorics
  • Zhanar Berikkyzy, Iowa State University
  • Christopher Cox, Carnegie Mellon University
  • Michael Dairyko, Iowa State University
  • Kirsten Hogenson, Colorado College
  • Mohit Kumbhat, University of Nevada, Reno
  • Bernard Lidicky, Iowa State University
  • Kacy Messerschmidt, Iowa State University
  • Kevin Moss, Iowa State University
  • Kathleen Nowak, Pacific Northwest National Laboratory
  • Kevin F. Palmowski, Iowa State University
  • Derrick Stolee, Microsoft Corporation
Document Type
Article
Publication Version
Submitted Manuscript
Publication Date
7-1-2017
DOI
10.1007/s00373-017-1812-5
Abstract

All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any ℓ ∈ {3, 4, 5, 6, 7}, a planar graph is 4-choosable if it is ℓ-cycle-free. In terms of constraining the list assignment, one refinement of k-choosability is choosability with separation. A graph is (k, s)-choosable if the graph is colorable from lists of size k where adjacent vertices have at most s common colors in their lists. Every planar graph is (4, 1)-choosable, but there exist planar graphs that are not (4, 3)-choosable. It is an open question whether planar graphs are always (4, 2)-choosable. A chorded ℓ-cycle is an ℓ-cycle with one additional edge. We demonstrate for each ℓ ∈ {5, 6, 7} that a planar graph is (4, 2)-choosable if it does not contain chorded ℓ-cycles.

Comments

This is a pre-print of an article published in Graphs and Combinatorics. The final authenticated version is available online at doi: 10.1007/s00373-017-1812-5.

Copyright Owner
Springer Japan
Language
en
File Format
application/pdf
Citation Information
Zhanar Berikkyzy, Christopher Cox, Michael Dairyko, Kirsten Hogenson, et al.. "(4, 2)-Choosability of Planar Graphs with Forbidden Structures" Graphs and Combinatorics Vol. 33 Iss. 4 (2017) p. 751 - 787
Available at: http://works.bepress.com/bernard-lidicky/30/