Infinitely many trees with maximum number of holes zero, one, and two (Q1741707)

Summary: An \(L(2,1)\)-coloring of a simple connected graph \(G\) is an assignment \(f\) of nonnegative integers to the vertices of \(G\) such that \(|f(u)-f(v)| \geqslant 2\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\geqslant 1\) if \(d(u,v)=2\) for all \(u,v\in V(G)\), where \(d(u,v)\) denotes the distance between \(u\) and \(v\) in \(G\). The span of \(f\) is the maximum color assigned by \(f\). The span of a graph \(G\), denoted by \(\lambda (G)\), is the minimum of span over all \(L(2,1)\)-colorings on \(G\). An \(L(2,1)\)-coloring of \(G\) with span \(\lambda(G)\) is called a span coloring of \(G\). An \(L(2,1)\)-coloring \(f\) is said to be irreducible if there exists no \(L(2,1)\)-coloring g such that \(g(u) \leqslant f(u)\) for all \(u \in V(G)\) and \(g(v) < f(v)\) for some \(v \in V(G)\). If \(f\) is an \(L(2,1)\)-coloring with span \(k\), then \(h \in\{0,1, 2, \dots, k\}\) is a hole if there is no \(v \in V(G)\) such that \(f(v)=h\). The maximum number of holes over all irreducible span colorings of \(G\) is denoted by \(H_\lambda (G)\). A tree \(T\) with maximum degree \(\Delta\) having span \(\Delta +1\) is referred to as Type-I tree; otherwise it is Type-II. In this paper, we give a method to construct infinitely many trees with at least one hole from a one-hole tree and infinitely many two-hole trees from a two-hole tree. Also, using the method, we construct infinitely many Type-II trees with maximum number of holes one and two. Further, we give a sufficient condition for a Type-II tree with maximum number of holes zero.