Proper conflict-free degree-choosability of outerplanar graphs

Abstract

A proper coloring $\ddot{I}•$ of $G$ is called a proper conflict-free coloring of $G$ if for every non-isolated vertex $v$ of $G$, there is a color $c$ such that $|\ddot{I}{•}^{-1}(c)\cap N_G(v)|=1$. As an analogy to degree-choosability of graphs, the authors recently, in a previous paper, introduced the notion of proper conflict-free $(\mathrm{degree}+k)$-choosability of graphs. For a non-negative integer $k$, a graph $G$ is proper conflict-free $(\mathrm{degree}+k)$-choosable if for any list assignment $L$ of $G$ with $|L(v)|\ge d_G(v)+k$ for every vertex $v\in V(G)$, $G$ admits a proper conflict-free coloring $\ddot{I}•$ such that $\ddot{I}•(v)\in L(v)$ for every vertex $v\in V(G)$. In this paper, we show that every connected outerplanar graph other than the $5$-cycle is proper conflict-free $(\mathrm{degree}+2)$-choosable. This bound is tight in the sense that there are infinitely many connected outerplanar graphs that are not proper conflict-free $(\mathrm{degree}+1)$-choosable. We conclude the paper with two questions for further work.

10 pages