A note on adaptable choosability and choosability with separation of planar graphs

Abstract

Let \( F \) be a (possibly improper) edge-coloring of a graph \( G \); a vertex coloring of \( G \) is adapted to \( F \) if no color appears at the same time on an edge and on its two endpoints. If for some integer \( k \), a graph \( G \) is such that given any list assignment \( L \) to the vertices of \( G \), with \( |L(v)| \geq k \) for all \( v \), and any edge-coloring \( F \) of \( G \), \( G \) admits a coloring \( c \) adapted to \( F \) where \( c(v) \in L(v) \) for all \( v \), then \( G \) is said to be adaptably k-choosable. A \((k,d)\)-list assignment for a graph \( G \) is a map that assigns to each vertex \( v \) a list \( L(v) \) of at least \( k \) colors such that \( |L(x) \cap L(y)| \leq d \) whenever \( x \) and \( y \) are adjacent. A graph is \((k,d)\)-choosable if for every \((k,d)\)-list assignment \( L \) there is an \( L \)-coloring of \( G \). It has been conjectured that planar graphs are \((3,1)\)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since \((k,1)\)-choosability is a special case of adaptable \( k \)-choosability, this implies that a planar graph satisfying these conditions is \((3,1)\)-choosable.