Some classes of trees with maximum number of holes two

Abstract

An (Formula presented.) -coloring of a simple connected graph (Formula presented.) is an assignment of non-negative integers to the vertices of (Formula presented.) 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 (Formula presented.) -coloring is called span of that coloring. The span of a graph (Formula presented.) denoted by (Formula presented.) is the smallest span taken over all (Formula presented.) -colorings of (Formula presented.). A hole is an unused color within the range of colors used by the coloring. An (Formula presented.) -coloring (Formula presented.) is said to be irreducible if no other (Formula presented.) -coloring can be produced by decreasing a color of (Formula presented.). The maximum number of holes of a graph (Formula presented.), denoted by (Formula presented.), is the maximum number of holes taken over all irreducible (Formula presented.) -colorings with span (Formula presented.). Laskar and Eyabi (Christpher, 2009) conjectured that if (Formula presented.) is a tree, then (Formula presented.) if and only if (Formula presented.), (Formula presented.). 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. Published with license by Taylor & Francis Group, LLC.