Derrick Stolee - Iowa State University - Research Browser
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.
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:
- 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.
There does exist a planar graph that is not (4,3)-choosable.
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
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