Skip to main navigation Skip to search Skip to main content

Packing edge-colorings of subcubic outerplanar graphs

  • Sijin Li
  • , Yifan Li
  • , Xujun Liu*
  • *Corresponding author for this work
  • University of Oxford

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)68-82
Number of pages15
JournalDiscrete Applied Mathematics
Volume391
DOIs
Publication statusPublished - 15 Oct 2026

Keywords

  • edge-coloring
  • Induced matching
  • Matching
  • Outerplanar graph
  • Packing edge-coloring
  • S-packing edge-coloring
  • Subcubic graph

Cite this