Originators: Jan Kratochvíl, Zsolt Tuza, Margit Voigt (presented by Suil O - REGS 2008)
Definitions: Given natural numbers p,q,r with q≤p and r≤p, a graph G is (p,q,r)-choosable if for every assignment L of lists to vertices such that |L(v)|=p for all v∈V and |L(u)∩L(v)|≤p-r for all adjacent pairs u,v&isin V(G), one can choose a q-element set F(v) for each v∈V(G) such that F(v)⊆L(v) for all v and |F(u)∩F(v)|=∅ for all uv∈E(G).
The notation is a bit awkward; it would seem more natural for the third parameter to give the upper bound on the overlap of adjacent lists rather than giving the lower bound on their difference. With this phrasing, every graph is (p,q,p)-choosable, and (p,q,0)-choosability is the same as (p,q)-choosability. Hence the question for a particular graph is how small r can be made.
Question 1 ([KTV]): Is every planar graph (4,1,2)-choosable?
Question 2 ([S]): Is every planar graph (3,1,2)-choosable?
Comments: Thomassen [T] proved that every planar graph is 5-choosable, which in this context means (5,1,0)-choosable. Kratochvíl, Tuza, and Voigt [KTV] proved that every planar graph is (4,1,3)-choosable; (4,1,2)-choosable would be stronger. Planar graphs that are not 4-choosable are not (4,1,0)-choosable. To obtain a proof that planar graphs are not (4,1,1)-choosable, one needs an example with lists of size 4 such that adjacent vertices have distinct lists and no proper coloring can be chosen from the lists. Gutner [G] provided such a construction. Škrekovski [S] gave another proof that planar graphs are (4,1,3)-choosable, constructed a planar graph that is not (3,1,1)-choosable, and posed Question 2 above.
References:
[G] Gutner, Shai; The complexity of planar graph choosability.
Discrete Math. 159 (1996), no. 1-3, 119--130.
[KTV] Kratochvíl, J., Tuza, Zs., Voigt, M.;
Brooks-type theorems for choosability with separation.
J. Graph Theory 27 (1998), no. 1, 43--49.
[S] Škrekovski, Riste, A note on choosability with separation for planar
graphs. Ars Combin. 58 (2001), 169--174.
[T] Thomassen, Carsten, Every planar graph is 5-choosable. J. Combin.
Theory Ser. B 62 (1994), no. 1, 180--181.