Geodesic
Solutions of Some L(2, 1)-Coloring Related Open Problems
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 279-297.

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

An L(2, 1)-coloring (or labeling) of a graph G is a vertex coloring 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 d(u, v) = 2, where d(u, v) is the distance between vertices u and v in G. The span of an L(2, 1)-coloring is the maximum color (or label) assigned by it. The span of a graph G is the smallest integer λ such that there exists an L(2, 1)-coloring of G with span λ. An L(2, 1)-coloring of a graph with span equal to the span of the graph is called a span coloring. For an L(2, 1)-coloring f of a graph G with span k, an integer h is a hole in f if h ∈ (0, k) and there is no vertex v in G such that f(v) = h. A no-hole coloring is an L(2, 1)-coloring with no hole in it. An L(2, 1)-coloring is irreducible if color of none of the vertices in the graph can be decreased to yield another L(2, 1)-coloring of the same graph. A graph G is inh-colorable if there exists an irreducible no-hole coloring of G. Most of the results obtained in this paper are answers to some problems asked by Laskar et al. [5]. These problems are mainly about relationship between the span and maximum no-hole span of a graph, lower inh-span and upper inh-span of a graph, and the maximum number of holes and minimum number of holes in a span coloring of a graph. We also give some sufficient conditions for a tree and an unicyclic graph to have inh-span Δ + 1.
Keywords: span of a graph, no-hole coloring, irreducible coloring, unicyclic graph, L(2 1)-coloring 
@article{DMGT_2016_36_2_a2,
     author = {Mandal, Nibedita and Panigrahi, Pratima},
     title = {Solutions of {Some} {L(2,} {1)-Coloring} {Related} {Open} {Problems}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {279--297},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a2/}
}
TY  - JOUR
AU  - Mandal, Nibedita
AU  - Panigrahi, Pratima
TI  - Solutions of Some L(2, 1)-Coloring Related Open Problems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 279
EP  - 297
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a2/
LA  - en
ID  - DMGT_2016_36_2_a2
ER  - 
%0 Journal Article
%A Mandal, Nibedita
%A Panigrahi, Pratima
%T Solutions of Some L(2, 1)-Coloring Related Open Problems
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 279-297
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a2/
%G en
%F DMGT_2016_36_2_a2
Mandal, Nibedita; Panigrahi, Pratima. Solutions of Some L(2, 1)-Coloring Related Open Problems. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 279-297. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a2/

[1] 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

[2] J.P. Georges, D.W. Mauro and M.A. Whittlesey, Relating path coverings to vertex labellings with a condition at distance two, Discrete Math. 135 (1994) 103-111. doi:10.1016/0012-365X(93)E0098-O

[3] 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

[4] R. Laskar and G. Eyabi, Holes in L(2, 1)-coloring on certain classes of graphs, AKCE Int. J. Graphs Comb. 6 (2009) 329-339.

[5] R.C. Laskar, J. Jacob and J. Lyle, Variations of graph coloring, domination and combinations of both: a brief survey, Advances in Discrete Mathematics and Appli- cations, Ramanujan Mathematical Society Lecture Notes Series 13 (2010) 133-152.

[6] 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

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

[8] W.F. Wang, The L(2, 1)-labelling of trees, Discrete Appl. Math. 154 (2006) 598-603. doi:10.1016/j.dam.2005.09.007

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

[10] M.Q. Zhai, C.H. Lu and J.L. Shu, A note on L(2, 1)-labelling of trees, Acta Math. Appl. Sin. Engl. Ser. 28 (2012) 395-400. doi:10.1007/s10255-012-0151-9