S-packing edge-colorings of subcubic outerplanar graphs
Preprint
Abstract
For a sequence $S = (s_1, s_2, \ldots, 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, \ldots, 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\v{z}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\v{z}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'$ and $k_2'$ such that every $2$-connected subcubic outerplanar graph is $(1,2^3,k_1')$-colorable and $(1^2,2^2,k_2')$-colorable?". We prove $k_1' = 2$ and $3 \le k_2' \le 11$.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorableJournal of Graph Theory, 2023
- Between proper and strong edge‐colorings of subcubic graphsJournal of Graph Theory, 2022
- Strong edge colorings of graphs and the covers of Kneser graphsJournal of Graph Theory, 2022
- On -packing edge-colorings of cubic graphsDiscrete Applied Mathematics, 2019
- Strong edge-coloring for planar graphs with large girthDiscrete Mathematics, 2019
- Packing chromatic number of cubic graphsDiscrete Mathematics, 2018
- Packing chromatic number under local changes in a graphDiscrete Mathematics, 2017
- -packing colorings of cubic graphsDiscrete Mathematics, 2016
- Induced matchings in cubic graphsJournal of Graph Theory, 1993
- The strong chromatic index of a cubic graph is at most 10Discrete Mathematics, 1992