L( $$d$$ d ,1)-labelings of the edge-path-replacement by factorization of graphs

For an integer $$d \ge 2$$ d ≥ 2 , an $$L(d$$ L ( d ,1)-labeling of a graph $$G$$ G is a function $$f$$ f from its vertex set to the non-negative integers such that $${\vert }f(x) - f(y){\vert } \ge d$$ | f ( x ) − f ( y ) | ≥ d if vertices $$x$$ x and $$y$$ y are adjacent, and $${\vert }f(x) - f(y){\vert } \ge $$ | f ( x ) − f ( y ) | ≥ 1 if $$x$$ x and $$y$$ y are at distance two. The minimum span over all the L( $$d$$ d ,1)-labelings of $$G$$ G is denoted by $$\lambda _{d}(G)$$ λ d ( G ) . For a given integer $$k \ge 2$$ k ≥ 2 , the edge-path-replacement of $$G$$ G or $$G(P_{k})$$ G ( P k ) is the graph obtained from $$G$$ G by replacing each edge with a path $$P_{k}$$ P k on $$k$$ k vertices. We show that the edges of $$G$$ G can be colored with $$\lceil \varDelta (G)/2\rceil $$ ⌈ Δ ( G ) / 2 ⌉ colors so that each monochromatic subgraph has maximum degree at most 2 and use this fact to establish general upper bounds on $$\lambda _{d}(G(P_{k}))$$ λ d ( G ( P k ) ) for $$k \ge 4$$ k ≥ 4 . As a corollary, we settle the following conjecture by Lü (J Comb Optim, 2012): for any graph $$G$$ G with $$\varDelta (G) \ge $$ Δ ( G ) ≥ 2, $$\lambda _{2}(G(P_{4})) \le \varDelta (G)$$ λ 2 ( G ( P 4 ) ) ≤ Δ ( G ) + 2. Moreover, $$\lambda _{2}(G(P_{4})) = \varDelta (G) + 1$$ λ 2 ( G ( P 4 ) ) = Δ ( G ) + 1 when $$\varDelta (G)$$ Δ ( G ) is even and different from 2. We also show that the class of graphs $$G(P_{k})$$ G ( P k ) with $$k \ge $$ k ≥ 4 satisfies a conjecture by Havet and Yu (2008 Discrete Math 308:498–513) in the related area of ( $$d,1$$ d , 1 )-total labeling of graphs.