Back to Search
Start Over
On [formula omitted]-packing edge-colorings of graphs with small edge weight.
- 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]
- Subjects :
- *BIPARTITE graphs
*EDGES (Geometry)
Subjects
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