Packing $(1,1,2,4)$-coloring of subcubic outerplanar graphs

Abstract

For $1\le s_1\le s_2\le \dots \le s_k$ and a graph $G$, a packing $(s_1,s_2,\dots ,s_k)$-coloring of $G$ is a partition of $V(G)$ into sets $V_1,V_2,\dots ,V_k$ such that, for each $1\le i\le k$, the distance between any two distinct $x,y\in V_i$ is at least $s_i+1$. The packing chromatic number, ${\chi }_p(G)$, of a graph $G$ is the smallest $k$ such that $G$ has a packing $(1,2,\dots ,k)$-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs $G$ with arbitrarily large ${\chi }_p(G)$. Recently, there was a series of papers on packing $(s_1,s_2,\dots ,s_k)$-colorings of subcubic graphs in various classes. We show that every $2$-connected subcubic outerplanar graph has a packing $(1,1,2)$-coloring and every subcubic outerplanar graph is packing $(1,1,2,4)$-colorable. Our results are sharp in the sense that there are $2$-connected subcubic outerplanar graphs that are not packing $(1,1,3)$-colorable and there are subcubic outerplanar graphs that are not packing $(1,1,2,5)$-colorable. We also show subcubic outerplanar graphs that are not packing $(1,2,2,4)$-colorable and not packing $(1,1,3,4)$-colorable.

13 pages, 5 figures