Back to Search Start Over

On [formula omitted]-packing edge-colorings of graphs with small edge weight.

Authors :
Yang, Wei
Wu, Baoyindureng
Source :
Applied Mathematics & Computation. Apr2022, Vol. 418, pN.PAG-N.PAG. 1p.
Publication Year :
2022

Abstract

• We confirm the question in affirmative with a stronger way. It is shown that for any graph G (not necessarily subcubic bipartite) with w (e) ≤ 5 is (1 , 2 4) -packing edge-colorable. • We also prove that every graph G with w (e) ≤ 6 is (1 , 2 8) -packing edge-colorable. • we prove that if G is cubic graph, then it has a (1 , 3 20) -packing edge-coloring and a (1 , 4 47) -packing edge-coloring. Furthermore, if G is 3-edge-colorable, then it has a (1 , 3 18) -packing edge-coloring and a (1 , 4 42) -packing edge-coloring. These strengthen results of Gastineau and Togni (On S -packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019) 63–75). The edge weight, denoted by w (e) , of a graph G is max { d G (u) + d G (v) : u v ∈ E (G) }. For an integer sequence S = (s 1 , s 2 , ... , s k) with 0 ≤ s 1 ≤ s 2 ≤ ⋯ ≤ s k , an S -packing edge-coloring of a graph G is a partition of E (G) into k subsets E 1 , E 2 , ... , E k such that for each 1 ≤ i ≤ k , d L (G) (e , e ′) ≥ s i + 1 for any e , e ′ ∈ E i , where d L (G) (e , e ′) denotes the distance of e and e ′ in the line graph L (G) of G. Hocquard, Lajou and Lužar (Between proper and strong edge-colorings of subcubic graphs, https://arxiv.org/abs/2011.02175) posed an open problem: every subcubic bipartite graph G with w (e) ≤ 5 is (1 , 2 4) -packing edge-colorable. We confirm the question in affirmative with a stronger way. It is shown that for any graph G (not necessarily subcubic bipartite) with w (e) ≤ 5 is (1 , 2 4) -packing edge-colorable. We also prove that every graph G with w (e) ≤ 6 is (1 , 2 8) -packing edge-colorable. In addition, we prove that if G is cubic graph, then it has a (1 , 3 20) -packing edge-coloring and a (1 , 4 47) -packing edge-coloring. Furthermore, if G is 3-edge-colorable, then it has a (1 , 3 18) -packing edge-coloring and a (1 , 4 42) -packing edge-coloring. These strengthen results of Gastineau and Togni (On S -packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019) 63–75). [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00963003
Volume :
418
Database :
Academic Search Index
Journal :
Applied Mathematics & Computation
Publication Type :
Academic Journal
Accession number :
154313917
Full Text :
https://doi.org/10.1016/j.amc.2021.126840