Irreducible No-Hole L(2, 1)-Coloring of Edge-Multiplicity-Paths-Replacement Graph

Mandal, Nibedita ; Panigrahi, Pratima

Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 525-552

Résumé

An L(2, 1)-coloring (or labeling) of a simple connected graph G is a mapping f : V (G) → Z⁺ ∪ 0 such that |f(u)−f(v)| ≥ 2 for all edges uv of G, and |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), of G is maxf(v) : v ∈ V (G). The span of G, denoted by λ(G), is the minimum span of all possible L(2, 1)-colorings of G. For an L(2, 1)-coloring f of a graph G with span k, an integer l is a hole in f if l ∈ (0, k) and there is no vertex v in G such that f(v) = l. An L(2, 1)-coloring is a no-hole coloring if there is no hole in it, and is an irreducible coloring if color of none of the vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring, in short inh-coloring, of G is an L(2, 1)-coloring of G which is both irreducible and no-hole. For an inh-colorable graph G, the inh-span of G, denoted by λ_inh(G), is defined as λ_inh(G) = minspan(f) : f is an inh-coloring of G. Given a function h : E(G) → ℕ − 1, and a positive integer r ≥ 2, the edge-multiplicity-paths-replacement graph G(rP_h) of G is the graph obtained by replacing every edge uv of G with r paths of length h(uv) each. In this paper we show that G(rP_h) is inh-colorable except possibly the cases h(e) ≥ 2 with equality for at least one but not for all edges e and (i) Δ(G) = 2, r = 2 or (ii) Δ (G) ≥ 3, 2 ≤ r ≤ 4. We find the exact value of λ_inh(G(rP_h)) in several cases and give upper bounds of the same in the remaining. Moreover, we find the value of λ(G(rP_h)) in most of the cases which were left by Lü and Sun in [L(2, 1)-labelings of the edge-multiplicity-paths-replacement of a graph, J. Comb. Optim. 31 (2016) 396–404].

Détail

Keywords: L (2,1)-coloring, no-hole coloring, irreducible coloring, subdivision graph, edge-multiplicity-paths-replacement graph