Article in press
Authors:
Title:
On $S$-packing edge-coloring of graphs with given edge weight
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-07-20 , Revised: 2025-05-25 , Accepted: 2025-06-01 , Available online: 2025-06-24 , https://doi.org/10.7151/dmgt.2591
Abstract:
Let $S=(s_1,\ldots, s_k)$ be a non-decreasing sequence of positive integers.
A graph $G=(V(G), E(G))$ is said to be $S$-packing edge-colorable if $E(G)$ can
be decomposed into disjoint sets $E_1,\ldots, E_k$ such that for every
$1\leq i\leq k$, the distance between any two distinct edges in $E_i$ is at
least $s_i+1$. The edge weight of $G$ is defined as $ew(G)=\max\{d(u)+d(v)|uv
\in E(G)\}$. A fork is the graph obtained from $K_{1,3}$ by subdividing an edge
once. In 2023, Liu et al. proved that every subcubic multigraph is
$(1, 2^7)$-packing edge-colorable. Based on the work of Liu et al., we
prove that every multigraph $G$ with $ew(G)\leq6$ is $(1, 2^7)$-packing
edge-colorable, which confirms a conjecture of Yang and Wu (2022). In addition,
we demonstrate that if $G$ is a fork-free graph with $ew(G)\leq6$, then $G$ is
$(1, 2^6)$-packing edge-colorable.
Keywords:
$S$-packing edge-coloring, edge weight, fork-free graphs
References:
- J.-L. Fouquet and J.-M. Vanherpe, On parsimonious edge-colouring of graphs with maximum degree three, Graphs Combin. 29 (2013) 475–487.
https://doi.org/10.1007/s00373-012-1145-3 - J.-L. Fouquet and J.L. Jolivet, Strong edge-colorings of graphs and applications to multi-$k$-gons, Ars Combin. 16A (1983) 141–150.
- N. Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019) 63–75.
https://doi.org/10.1016/j.dam.2018.12.035 - W. Goddard and H. Xu, The S-packing chromatic number of a graph, Discuss. Math. Graph Theory 32 (2012) 795–806.
https://doi.org/10.7151/dmgt.1642 - P. Hall, On representatives of subsetes, J. Lond. Math. Soc. 10 (1935) 26–30.
https://doi.org/10.1112/jlms/s1-10.37.26 - H. Hocquard, D. Lajou and B. Lužar, Between proper and strong edge-colorings of subcubic graphs, J. Graph Theory 101 (2022) 686–716.
https://doi.org/10.1002/jgt.22848 - X.J. Liu, M. Santana and T. Short, Every subcubic multigraph is $(1, 2^7)$-packing edge-colorable, J. Graph Theory 104 (2023) 851–885.
https://doi.org/10.1002/jgt.23004 - X. J. Liu and G. Yu, On the $(1^2,2^4)$-packing edge-coloring of subcubic graphs (2024).
arXiv: 2402.18353v1 - K. Nakprasit, A note on the strong chromatic index of bipartite graphs, Discrete Math. 308 (2008) 3726–3728.
https://doi.org/10.1016/j.disc.2007.07.034 - V.G. Vizing, On an estimate of the chromatic class of a $p$-graph, Diskret. Analiz. 3 (1964) 25–30, in Russian.
- W. Yang and B. Wu, On $S$-packing edge-colorings of graphs with small edge weight, Appl. Math. Comput. 418 (2022) 126840.
https://doi.org/10.1016/j.amc.2021.126840
Close