Some classes of trees with maximum number of holes two

Abstract

An L2,1-coloring of a simple connected graph G is an assignment of non-negative integers to the vertices of G such that adjacent vertices color difference is at least two, and vertices that are at distance two from each other get different colors. The maximum color assigned in an L2,1-coloring is called span of that coloring. The span of a graph G denoted by ?G is the smallest span taken over all L2,1-colorings of G. A hole is an unused color within the range of colors used by the coloring. An L2,1-coloring f is said to be irreducible if no other L2,1-coloring can be produced by decreasing a color of f. The maximum number of holes of a graph G, denoted by H?G, is the maximum number of holes taken over all irreducible L2,1-colorings with span ?G. Laskar and Eyabi (Christpher, 2009) conjectured that if T is a tree, then H?T=2 if and only if T=Pn, n>4. We show that this conjecture does not hold by providing a counterexample. Also, we give some classes of trees with maximum number of holes two. 2018 Kalasalingam University