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

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 -