Geodesic
Irreducible No-Hole L(2, 1)-Coloring of Edge-Multiplicity-Paths-Replacement Graph
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 525-552.

Voir la notice de l'article provenant de la source Library of Science

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(rPh) 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(rPh) 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(rPh)) in several cases and give upper bounds of the same in the remaining. Moreover, we find the value of λ(G(rPh)) 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].
Keywords: L (2,1)-coloring, no-hole coloring, irreducible coloring, subdivision graph, edge-multiplicity-paths-replacement graph 
@article{DMGT_2018_38_2_a14,
     author = {Mandal, Nibedita and Panigrahi, Pratima},
     title = {Irreducible {No-Hole} {L(2,} {1)-Coloring} of {Edge-Multiplicity-Paths-Replacement} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {525--552},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a14/}
}
TY  - JOUR
AU  - Mandal, Nibedita
AU  - Panigrahi, Pratima
TI  - Irreducible No-Hole L(2, 1)-Coloring of Edge-Multiplicity-Paths-Replacement Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 525
EP  - 552
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a14/
LA  - en
ID  - DMGT_2018_38_2_a14
ER  - 
%0 Journal Article
%A Mandal, Nibedita
%A Panigrahi, Pratima
%T Irreducible No-Hole L(2, 1)-Coloring of Edge-Multiplicity-Paths-Replacement Graph
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 525-552
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a14/
%G en
%F DMGT_2018_38_2_a14
Mandal, Nibedita; Panigrahi, Pratima. Irreducible No-Hole L(2, 1)-Coloring of Edge-Multiplicity-Paths-Replacement Graph. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 525-552. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a14/

[1] F.-H. Chang, M.-L. Chia, D. Kuo, S.-C. Liaw and M.-H. Tsai, L (2, 1)- labelings of subdivisions of graphs, Discrete Math. 338 (2015) 248–255. doi:10.1016/j.disc.2014.09.006

[2] G.J. Chang and C. Lu, Distance-two labelings of graphs, European J. Combin. 24 (2003) 53–58. doi:10.1016/S0195-6698(02)00134-8

[3] P.C. Fishburn and F.S. Roberts, No-hole L (2, 1)- colorings, Discrete Appl. Math. 130 (2003) 513–519. doi:10.1016/S0166-218X(03)00329-9

[4] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595. doi:10.1137/0405048

[5] F. Havet and M.-L. Yu, ( p, 1)-total labelling of graphs, Technical Report 4650, INRIA (2002).

[6] F. Havet and M.-L. Yu, ( p, 1)- total labelling of graphs, Discrete Math. 308 (2008) 496–513. doi:10.1016/j.disc.2007.03.034

[7] J. Jacob, R. Laskar and J.Villalpando, On the irreducible no-hole L (2, 1) coloring of bipartite graphs and Cartesian products, J. Combin. Math. Combin. Comput. 78 (2011) 49–64.

[8] N. Karst, J. Oehrlein, D.S. Troxell and J. Zhu, L ( d, 1)- labelings of the edge-pathreplacement by factorization of graphs, J. Comb. Optim. 30 (2015) 34–41. doi:10.1007/s10878-013-9632-x

[9] R.C. Laskar, G.L. Matthews, B. Novick and J. Villalpando, On irreducible no-hole L (2, 1)- coloring of trees, Networks 53 (2009) 206–211. doi:10.1002/net.20286

[10] R.C. Laskar and J.J. Villalpando, Irreducibility of L (2, 1)- coloring and inh-colorablity of unicyclic and hex graphs, Util. Math. 69 (2006) 65–83.

[11] D. Lü, L (2, 1)- labelings of the edge-path-replacement of a graph, J. Comb. Optim. 26 (2013) 385–392. doi:10.1007/s10878-012-9470-2

[12] D. Lü and J. Sun, L (2, 1)- labelings of the edge-multiplicity-paths-replacement of a graph, J. Comb. Optim. 31 (2016) 396–404. doi:10.1007/s10878-014-9761-x

[13] N. Mandal and P. Panigrahi, On irreducible no-hole L (2, 1)- coloring of subdivision of graphs, J. Comb. Optim. 33 (2017) 1421–1442. doi:10.1007/s10878-016-0047-3

[14] D.B. West, Introduction to Graph Theory (New Delhi, Prentice-Hall, 2003).

[15] M.A. Whittlesey, J.P. Georges and D.W. Mauro, On the λ- number of Qn and related graphs, SIAM J. Discrete Math. 8 (1995) 499–506. doi:10.1137/S0895480192242821