On irreducible no-hole L(2, 1)-coloring of subdivision of graphs

An L(2, 1)-coloring (or labeling) of a graph G is a mapping $$f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}$$ f : V ( G ) → Z + ⋃ { 0 } such that $$|f(u)-f(v)|\ge 2$$ | f ( u ) - f ( v ) | ≥ 2 for all edges uv of G, and $$|f(u)-f(v)|\ge 1$$ | f ( u ) - f ( v ) | ≥ 1 if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by $$\lambda (G)$$ λ ( G ) , is min {span $$f: f\text {is an }L(2,1)\text {-coloring of } G\}$$ f : f is an L ( 2 , 1 ) -coloring of G } . If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if $$l\in (0,k)$$ l ∈ ( 0 , k ) and there is no vertex v in G such that $$f(v)=l$$ f ( v ) = l . A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from $$\{0,1,\ldots ,k\}$$ { 0 , 1 , … , k } , for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by $$\lambda _{inh}(G)$$ λ i n h ( G ) , is defined as $$\lambda _{inh}(G)=\min ~\{$$ λ i n h ( G ) = min { span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to $$\mathbb {N}$$ N , the h-subdivision of G, denoted by $$G_{(h)}$$ G ( h ) , is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that $$G_{(h)}$$ G ( h ) is inh-colorable for $$h(e)\ge 2$$ h ( e ) ≥ 2 , $$e\in E(G)$$ e ∈ E ( G ) , except the case $$\Delta =3$$ Δ = 3 and $$h(e)=2$$ h ( e ) = 2 for at least one edge but not for all. Moreover we find the exact value of $$\lambda _{inh}(G_{(h)})$$ λ i n h ( G ( h ) ) in several cases and give upper bounds of the same in the remaining.