2017/11/29 by Nicolas Gastineau, Gastineau, Nicolas, Olivier Togni +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1711.10906
arxiv created 2017/11/29 · openalex publication_date 2017/11/29 · arxiv updated 2017/11/30 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
Given a non-decreasing sequence S = (s 1,s 2,. .. ,s k) of positive integers, an S-packing edge-coloring of a graph G is a partition of the edge set of G into k subsets X 1 ,X 2,. .. ,X k such that for each 1 ≤ i ≤ k, the distance between two distinct edges e, e ' ∈ X i is at least s i + 1. This paper studies S-packing edge-colorings of cubic graphs. Among other results, we prove that cubic graphs having a 2-factor are (1,1,1,3,3)-packing edge-colorable, (1,1,1,4,4,4,4,4)-packing edge-colorable and (1,1,2,2,2,2,2)-packing edge-colorable. We determine sharper results for cubic graphs of bounded oddness and 3-edge-colorable cubic graphs and we propose many open problems.