Packing edge-colorings of subcubic outerplanar graphs

Abstract

For a sequence $S=(s_1,s_2,\dots ,s_k)$ of non-decreasing positive integers, an $S$-packing edge-coloring (S-coloring) of a graph $G$ is a partition of $E(G)$ into $E_1,E_2,\dots ,E_k$ such that the distance between each pair of distinct edges $e_1,e_2\in E_i$, $1\le i\le k$, is at least $s_i+1$. In particular, a $(1^{\ell },2^k)$-coloring is a partition of $E(G)$ into $\ell$ matchings and $k$ induced matchings, and it can be viewed as intermediate colorings between proper and strong edge-colorings. Hocquard, Lajou, and Lužar conjectured that every subcubic planar graph has a $(1,2^6)$-coloring and a $(1^2,2^3)$-coloring. In this paper, we confirm the conjecture of Hocquard, Lajou, and Lužar for subcubic outerplanar graphs by showing every subcubic outerplanar graph has a $(1,2^5)$-coloring and a $(1^2,2^3)$-coloring. Our results are best possible since we found subcubic outerplanar graphs with no $(1,2^4)$-coloring and no $(1^2,2^2)$-coloring respectively. Furthermore, we explore the question "What is the largest positive integer $k_1$ and $k_2$ such that every subcubic outerplanar graph is $(1,2^4,k_1)$-colorable and $(1^2,2^2,k_2)$-colorable?". We prove $3\le k_1\le 6$ and $3\le k_2\le 4$. We also consider the question "What is the largest positive integer $k_1^{\prime }$ and $k_2^{\prime }$ such that every $2$-connected subcubic outerplanar graph is $(1,2^3,k_1^{\prime })$-colorable and $(1^2,2^2,k_2^{\prime })$-colorable?". We prove $k_1^{\prime }=2$ and $3\le k_2^{\prime }\le 11$.

20 pages, 9 figures