Some classes of trees with maximum number of holes two
Srinivasa Rao Kola, Balakrishna Gudla, P. K. Niranjan · AKCE International Journal of Graphs and Combinatorics · 2018
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.