Single conflict coloring, adaptable choosability and separation choosability

Abstract

We study relations between three interrelated notions of graph (list) coloring: single conflict coloring, adapted list coloring and choosability with separation (with $1$ overlapping color between lists of adjacent vertices), and their respective invariants single conflict chromatic number $\ddot{I}{‡}_{\nleftrightarrow }$, adaptable choosability $c{h}_{ad}$ and separation choosability $c{h}_{sep}$. We investigate graphs with small values of these invariants, and construct explicit families of graphs $G$ with $\ddot{I}{‡}_{\nleftrightarrow }(G)=c{h}_{ad}(G)>c{h}_{sep}(G)$, as well as where all three invariants are equal. Furthermore, we consider planar graphs and investigate for which triples $(a,b,c)$, there is a planar graph $G$ with $(c{h}_{sep}(G),c{h}_{ad}(G),\ddot{I}{‡}_{\nleftrightarrow }(G))=(a,b,c)$. Throughout the paper we pose many questions on these graph coloring parameters, and discuss connections to related coloring invariants such as adapted coloring.