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:

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.

Derrick Stolee - Iowa State University - Research Browser