Derrick Stolee - Iowa State University - Research Browser

Choosability with Separation for Planar Graphs
Problem and Results Summary

For integers k and d, a (k, d)-list assignment is a list assignment L on the vertices of a graph such that every vertex v has a list of size at least k and any pair u, v of adjacent vertices have at most d elements in both lists L(u) and L(v). A graph is (k, d)-choosable if there is a proper L-coloring for every (k, d)-list assignment L.

It is conjectured that every planar graph is (3,1)-choosable and (4,2)-choosable.

Choi, Lidický, and Stolee prove that planar graphs are (3,1)-choosable when certain cycles are forbidden:

1. Planar graphs with no 3-cycles are (3,1)-choosable.
2. Planar graphs with no 4-cycles are (3,1)-choosable.
3. Planar graphs with no 5- or 6-cycles are (3,1)-choosable.
There does exist a planar graph with no 4- or 5-cycles that is not (3,2)-choosable.

The Discrete Mathematics Working Seminar 2014-15 proved that planar graphs are (4,2)-choosable when certain structures are forbidden:

1. Planar graphs with no chorded 5-cycles are (4,2)-choosable.
2. Planar graphs with no chorded 6-cycles are (4,2)-choosable.
3. Planar graphs with no chorded 7-cycles are (4,2)-choosable.
4. Planar graphs with no doubly-chorded 6- or 7-cycles are (4,2)-choosable.
There does exist a planar graph that is not (4,3)-choosable.

Research Papers
Z. Berikkyzy, C. Cox, M. Dairyko, K. Hogenson, M. Kumbhat, B. Lidický, K. Messerschmidt, K. Moss, K. Nowak, K. F. Palmowski, D. Stolee, $(4,2)$-choosability of planar graphs with forbidden structures, submitted.
Web Version
I. Choi, B. Lidický, D. Stolee, On Choosability with Separation of Planar Graphs with Forbidden Cycles, to appear in Journal of Graph Theory
Web Version ArXiv Version Official Version
Related Work
Z. Füredi, A. Kostochka, and M. Kumbhat. Choosability with separation of complete multipartite graphs and hypergraphs, 2011.
ArXiv version
H. Kierstead, B. Lidický. On choosability with separation of planar graphs with lists of different sizes, 2013.
ArXiv version
C. Thomassen. 3-list-coloring planar graphs of girth 5. J. Combin. Theory Ser. B, 64:101-107, 1995. Official Version

Derrick Stolee - Iowa State University - Research Browser