Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

7-2017

Journal or Book Title

Graphs and Combinatorics

Volume

33

Issue

4

First Page

751

Last Page

787

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}" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">ℓ∈{3,4,5,6,7}ℓ∈{3,4,5,6,7}, a planar graph is 4-choosable if it is ℓ" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">ℓℓ-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ℓ" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">ℓℓ-cycle is an ℓ" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">ℓℓ-cycle with one additional edge. We demonstrate for each ℓ∈{5,6,7}" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">ℓ∈{5,6,7}ℓ∈{5,6,7} that a planar graph is (4, 2)-choosable if it does not contain chorded ℓ" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">ℓℓ-cycles.

Comments

The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-017-1812-5. Berikkyzy, Zhanar, Christopher Cox, Michael Dairyko, Kirsten Hogenson, Mohit Kumbhat, Bernard Lidický, Kacy Messerschmidt et al. "(4, 2)-choosability of planar graphs with forbidden structures." Graphs and Combinatorics 33, no. 4 (2017): 751-787." Posted with Permission

Copyright Owner

Springer Japan

Language

en

File Format

application/pdf

Published Version

Share

COinS