Solutions of Some L(2, 1)-Coloring Related Open Problems

Nibedita Mandal; Pratima Panigrahi

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 279-297
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Nibedita Mandal, and Pratima Panigrahi. "Solutions of Some L(2, 1)-Coloring Related Open Problems." Discussiones Mathematicae Graph Theory 36.2 (2016): 279-297. <http://eudml.org/doc/277115>.

@article{NibeditaMandal2016,
abstract = {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.},
author = {Nibedita Mandal, Pratima Panigrahi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {L(2; 1)-coloring; span of a graph; no-hole coloring; irreducible coloring; unicyclic graph; -coloring},
language = {eng},
number = {2},
pages = {279-297},
title = {Solutions of Some L(2, 1)-Coloring Related Open Problems},
url = {http://eudml.org/doc/277115},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Nibedita Mandal
AU - Pratima Panigrahi
TI - Solutions of Some L(2, 1)-Coloring Related Open Problems
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 279
EP - 297
AB - 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.
LA - eng
KW - L(2; 1)-coloring; span of a graph; no-hole coloring; irreducible coloring; unicyclic graph; -coloring
UR - http://eudml.org/doc/277115
ER -

References

top
  1. [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[Crossref] 
  2. [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[Crossref] Zbl0811.05058
  3. [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[Crossref] 
  4. [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. Zbl1210.05033
  5. [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. Zbl1244.05002
  6. [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[Crossref] Zbl1167.05026
  7. [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. Zbl1123.05040
  8. [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[Crossref] 
  9. [9] D.B. West, Introduction to Graph Theory (New Delhi, Prentice-Hall, 2003). 
  10. [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[Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.