Some classes of trees with maximum number of holes two

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

Abstract licence: CC BY-NC

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.