A (k,d)(k,d)-list assignment LL of a graph GG is a mapping that assigns to each vertex vv a list L(v)L(v) of at least kk colors and for any adjacent pair xyxy, the lists L(x)L(x) and L(y)L(y) share at most dd colors. A graph GG is (k,d)(k,d)-choosable if there exists an LL-coloring of GG for every (k,d)(k,d)-list assignment LL. This concept is also known as choosability with separation.
It is known that planar graphs are (4, 1)-choosable but it is not known if planar graphs are (3, 1)-choosable. We strengthen the result that planar graphs are (4, 1)-choosable by allowing an independent set of vertices to have lists of size 3 instead of 4.
Our strengthening is motivated by the observation that in (4, 1)-list assignment, vertices of an edge have together at least 7 colors, while in (3, 1)-list assignment, they have only at least 5. Our setting gives at least 6 colors.
Available at: http://works.bepress.com/bernard-lidicky/36/
This article is published as Kierstead, Hal A., and Bernard Lidický. "On choosability with separation of planar graphs with lists of different sizes." Discrete Mathematics 338, no. 10 (2015): 1779-1783. doi: 10.1016/j.disc.2015.01.008. Posted with permission.