Abstract
For a sequence S=(s1,s2,…,sk) of non-decreasing positive integers, an S-packing edge-coloring (S-coloring) of a graph G is a partition of E(G) into E1,E2,…,Ek such that the distance between each pair of distinct edges e1,e2∈Ei, 1≤i≤k, is at least si+1. In particular, a (1ℓ,2k)-coloring is a partition of E(G) into ℓ 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,26)-coloring and a (12,23)-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,25)-coloring and a (12,23)-coloring. Our results are the best possible since we found subcubic outerplanar graphs with no (1,24)-coloring and no (12,22)-coloring respectively. Furthermore, we explore the question “What are the largest positive integer k1 and k2 such that every subcubic outerplanar graph is (1,24,k1)-colorable and (12,22,k2)-colorable?”. We prove 3≤k1≤6 and 3≤k2≤4. We also consider the question “What are the largest positive integer k1′ and k2′ such that every 2-connected subcubic outerplanar graph is (1,23,k1′)-colorable and (12,22,k2′)-colorable?”. We prove k1′=2 and 3≤k2′≤11.
| Original language | English |
|---|---|
| Pages (from-to) | 68-82 |
| Number of pages | 15 |
| Journal | Discrete Applied Mathematics |
| Volume | 391 |
| DOIs | |
| Publication status | Published - 15 Oct 2026 |
Keywords
- edge-coloring
- Induced matching
- Matching
- Outerplanar graph
- Packing edge-coloring
- S-packing edge-coloring
- Subcubic graph
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver