Solutions of some L(2,1)-coloring related open problems
Nibedita Mandal, Pratima Panigrahi · Discussiones Mathematicae Graph Theory · 2015
An L(2, 1)-coloring (or labeling) of a graph G is a vertex coloring f : , 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. 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.