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:

- Planar graphs with no 3-cycles are (3,1)-choosable.
- Planar graphs with no 4-cycles are (3,1)-choosable.
- Planar graphs with no 5- or 6-cycles are (3,1)-choosable.

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

- Planar graphs with no chorded 5-cycles are (4,2)-choosable.
- Planar graphs with no chorded 6-cycles are (4,2)-choosable.
- Planar graphs with no chorded 7-cycles are (4,2)-choosable.
- Planar graphs with no doubly-chorded 6- or 7-cycles are (4,2)-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

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

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

ArXiv version

H. Kierstead, B. Lidický. On choosability with separation of planar graphs with lists of different sizes, 2013.

ArXiv version

ArXiv version

C. Thomassen. 3-list-coloring planar graphs of girth 5. *J. Combin. Theory Ser. B*, 64:101-107, 1995.
Official Version