(4, 2)-Choosability of Planar Graphs with Forbidden Structures

Thumbnail Image
Date
2017-07-01
Authors
Berikkyzy, Zhanar
Cox, Christopher
Dairyko, Michael
Hogenson, Kirsten
Kumbhat, Mohit
Messerschmidt, Kacy
Moss, Kevin
Nowak, Kathleen
Palmowski, Kevin
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
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.

Rights Statement
Copyright
Sun Jan 01 00:00:00 UTC 2017
Funding
DOI
Supplemental Resources
Collections