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)|\ge 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)|\le 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.