2024/11/08 by S. Li, Yifan Li, Li, Sijin +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.05720
openalex publication_date 2024/11/08 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/28
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 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 is 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 is 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.