# Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two

Authors: Srinivasa Rao Kola; Balakrishna Gudla; P. K. Niranjan
Journal: Journal of Applied Mathematics
 (2018)

---

## Abstract

AnL(2,1)-coloring of a simple connected graph G is an assignment f of nonnegative integers to the vertices of G such that fu-fv⩾2 if d(u,v)=1 and fu-fv⩾1 if d(u,v)=2 for all u,v∈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 λ(G), is the minimum of span over all L(2,1)-colorings on G. An L(2,1)-coloring of G with span λ(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)⩽f(u) for all u∈V(G) and g(v)<f(v) for some v∈V(G). If f is an L(2,1)-coloring with span k, then h∈0,1,2,…,k is a hole if there is no v∈V(G) such that f(v)=h. The maximum number of holes over all irreducible span colorings of G is denoted by Hλ(G). A tree T with maximum degree Δ having span Δ+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.


---

## Body

## 1. Introduction

The channel assignment problem is the problem of assigning frequencies to transmitters in some optimal manner. In 1992, Griggs and Yeh [1] have introduced the concept of L(2,1)-coloring as a variation of channel assignment problem. The distance between two vertices u and v in a graph G, denoted by d(u,v), is defined as the length of a shortest path between u and v in G. An L(2,1)-coloring of a graph G is an assignment f:V(G)→0,1,2,…,k such that, for every u,v in V(G), fu-fv⩾2 if u and v are adjacent and |f(u)-f(v)|⩾1 if u and v are at distance 2. The nonnegative integers assigned to the vertices are also called colors. The span of f, denoted by spanf, is max⁡fv:v∈VG. The span of G, denoted by λ(G), is min⁡{spanf:fisanL(2,1)-coloringofG}. An L(2,1)-coloring with span λ(G) is called a span coloring. A tree is a connected acyclic graph. In the introductory paper, Griggs and Yeh [1] proved that λ(Pn)=4 for n⩾5; λ(T) is either Δ+1 or Δ+2 for any tree T with maximum degree Δ. We refer to a tree as Type-I if λ(T)=Δ+1; otherwise it is Type-II. In a graph G with maximum degree Δ, we refer to a vertex v as a major vertex if its degree is Δ; otherwise v is a minor vertex. Wang [2] has proved that a tree with no pair of major vertices at distances 1, 2, and 4 is Type-I. Zhai et al. [3] have improved the above condition as a tree with no pair of major vertices at distances 2 and 4 is Type-I. Mandal and Panigrahi [4] have proved that λ(T)=Δ+1 if T has at most one pair of major vertices at distance either 2 or 4 and all other pairs are at distance at least 7. Wood and Jacob [5] have given a complete characterization of the L(2,1)-span of trees up to twenty vertices.Fishburn and Roberts [6] have introduced the concept of no-hole L(2,1)-coloring of a graph. If f is an L(2,1)-coloring of a graph G with span k, then an integer h∈0,1,2,…,k is called a hole in f if there is no vertex v in G such that f(v)=h. An L(2,1)-coloring with no hole is called a no-hole coloring of G. Fishburn et al. [7] have introduced the concept of irreducibility of L(2,1)-coloring. An L(2,1)-coloring of a graph G is reducible if there exists another L(2,1)-coloring g of G such that g(u)⩽f(u) for all vertices u in G and there exists a vertex v in G such that g(v)<f(v). If f is not reducible then it is called irreducible. An irreducible no-hole coloring is referred to as inh-coloring. A graph is inh-colorable if there exists an inh-coloring. For an inh-colorable graph G, the lower inh-span or simply inh-span of G, denoted by λinh(G), is defined as λinh(G)=min⁡{spanf:fisaninh-coloringofG}. Fishburn et al. [7] have proved that paths, cycles, and trees are inh-colorable except C3, C4, and stars. In addition to that, they showed that Δ+1⩽λinh(T)⩽Δ+2 where T is any nonstar tree. Laskar et al. [8] have proved that any nonstar tree T is inh-colorable and λinh(T)=λ(T). The maximum number of holes over all irreducible span colorings of G is denoted by Hλ(G). Laskar and Eyabi [9] have determined the exact values for maximum number of holes for paths, cycles, stars, and complete bipartite graphs as 2, 2, 1, and 1, respectively, and conjectured that, for any tree T, Hλ(T)=2 if and only if T is a path Pn,n>4. S. R. Kola et al. [10] have disproved the conjecture by giving a two-hole irreducible span coloring for a Type-II tree other than path.In this article, we give a method of construction of infinitely many two-hole trees from a two-hole tree and infinitely many trees with at least one hole from a one-hole tree. Also, we find maximum number of holes for some Type-II trees given by Wood and Jacob [5] and obtain infinitely many Type-II trees of holes one and two by applying the method of construction. Further, we give a sufficient condition for a zero-hole Type-II tree.


## 2. Construction of Trees with Maximum Number of Holes One and Two

We start this section with a lemma which gives the possible colors to the major vertices in a two-hole span coloring of a Type-II tree.Lemma 1.
In any two-hole span coloring of a Type-II treeT with Δ⩾3, all major vertices receive either the same color or the colors from any one of the sets {0,2}, {0,Δ+2}, or {Δ,Δ+2}.Proof.
Letf be a two-hole span coloring of a Type-II tree T. Suppose that v1 and v2 are major vertices such that f(v1)≠f(v2). First, we prove that {f(v1),f(v2)}={0,2} or {0,Δ+2} or {Δ,Δ+2}. Let f(v1)=l and f(v2)=l′. Without loss of generality, we assume that 0⩽l<l′⩽Δ+2. If l=0, then the color 1 must be one of the two holes in f. If l′≠Δ+2, then l′-1 and l′+1 are the holes. Since l′+1 cannot be 1, l′-1 is 1 which implies l′=2. If l≠0, then l-1 and l+1 are the holes in f. If l′≠Δ+2, then l′-1 and l′+1 are the holes which are not possible as l≠l′. If l′=Δ+2, then Δ+1 must be one of the holes in f. Since l-1 cannot be Δ+1, l+1 is Δ+1 which implies l=Δ.
If{f(v1),f(v2)}={0,2}, then 1 and 3 are the holes. If any major vertex v receives a color l other than 0 and 2, then the neighbors of v cannot get the colors 1 and 3 and at least one of l-1 and l+1(ifl=Δ+2,thenl-1). This is not possible as we need Δ+1 number of colors to color a major vertex and its neighbors. Similarly, other cases can be proved.The following lemma is a direct implication of Lemma1.Lemma 2.
Iff is a two-hole span coloring of a Type-II tree T having two major vertices at distance less than or equal to two, then the set of holes in f is {1,3}, {1,Δ+1}, or {Δ-1,Δ+1}.When we say connecting two trees, we mean adding an edge between them. Corresponding to the possibilities of holes given in Lemma2, we give a list of trees which can be connected to a two-hole tree having two major vertices at distance less than or equal to two, to obtain infinitely many two-hole trees. Later, we give a list of trees which can be connected to a one-hole tree to get infinitely many one-hole trees.Theorem 3.
IfT is a tree with maximum number of holes two and having at least two major vertices at distance at most two, then there are infinitely many trees with maximum number of holes two and with maximum degree Δ same as that of T.Proof.
Letf be an irreducible span coloring of T with two holes. Then by Lemma 2, the set of holes in f is {1,3} or {1,Δ+1} or {Δ-1,Δ+1}. Now, we give a method to construct trees from T using the coloring f and holes in f. For all the three possibilities of holes, we give a list of trees which can be connected to T to get a bigger tree with maximum number of holes two. Suppose 1 and 3 are the holes in f. We use Table 1 for construction.
Letu be a vertex of the tree T and c be the color received by u. Now depending on the colors of the neighbors of u, to preserve L(2,1)-coloring, we connect the trees (one at a time) given in Table 1 by adding an edge between u of T and the vertex colored k of tree in the table. Note that 0⩽k⩽Δ+2 and the color k is not equal to any of the colors c-1, c, c+1, 1, and 3 and not assigned to any neighbor of u. To maintain irreducibility, we use the condition given in the last column of the table. It is easy to see that, after every step, we get a tree T′ with maximum degree same as that of T and a two-hole irreducible span coloring of T′. Also, it is clear that T is a subtree of T′. Since connecting a tree to any pendant vertex is always possible, we get infinitely many trees.
Suppose1 and Δ+1 are the holes in f. Construction is similar to the previous case using trees in Table 2.
SupposeΔ-1 and Δ+1 are the holes in f. We use trees in Table 3 for construction.Table 1
Trees connectable to a vertexu colored c in a two-hole tree with 1 and 3 as holes.
Color of vertex Connectable trees Condition c = 0  k = 2 k > 3 and all colors greater than 3 less than k adjacent to c. k > 4 k > 5 3 < k ′ < k - 1 3 < k < k ′ - 1   c = 2  k ≠ 1,2 , 3 and all colors less than k adjacent to c. 3 < k ⩽ Δ and all colors less than k adjacent to c. k > 5 3 < k < k ′ - 1 3 < k ′ < k - 1 k > 5 k > c + 1   c>3  k = 0 k > 3 and all colors greater than 3 less than k adjacent to c. k > c + 1 k > 5 T 1 k > 4 T 2 5 < k < c - 1 T 3 3 < k ′ < k - 1 and c≠k′ T 4 3 < k < k ′ - 1 and c≠k′Table 2
Trees connectable to a vertexu colored c in a two-hole tree with 1 and Δ+1 as holes.
Color of vertex Connectable trees Condition c = 0  1 < k ⩽ Δ and all colors less than k adjacent to c. k > 3 and all colors greater than 3 less than k adjacent to c. 2 < k < k ′ - 1 < Δ or 2<k⩽Δ and k′=Δ+2 3 < k ′ < k - 1 < Δ or k=Δ+2 and k′=Δ 3 < k ⩽ Δ 3 < k ⩽ Δ or k=Δ+2  1 < c ⩽ Δ  k = 0 2 ⩽ k ⩽ Δ and all colors less than k adjacent to c k > 3 and all colors greater than 3 less than k adjacent to c. T 1 k > 3 and c≠2 T 2 5 ⩽ k < c - 1 2 < k ⩽ Δ or k=Δ+2 c + 1 < k ⩽ Δ or k=Δ+2 c ≠ k ′ and 1<k<k′-1<Δ c ≠ k ′ and 1<k′<k-1<Δ  c = Δ + 2  k = 0 2 ⩽ k ⩽ Δ and all colors less than k adjacent to c k > 3 and all colors greater than 3 less than k adjacent to c. T 1 5 ⩽ k ⩽ Δ T 2 5 ⩽ k ⩽ Δ T 3 2 < k ⩽ Δ T 5 1 < k ′ < k - 1 < Δ T 6 1 < k < k ′ - 1 < ΔTable 3
Trees connectable to a vertexu colored c in a two-hole tree with Δ-1 and Δ+1 as holes.
Color of vertex Connectable trees Condition 0 ⩽ c < Δ - 1  0 ⩽ k < Δ - 1 and all colors less than k adjacent to c. 2⩽k<c-1 c ≠ k ′ and 0⩽k′<k-1<Δ-2 or k=k′+2=Δ+2 or Δ c ≠ k ′ and 0⩽k<k′-1<Δ-2 or 0⩽k⩽Δ-2 and k′=Δ c + 1 < k ⩽ Δ - 2 or k=Δ k=Δ k=Δ+2  c = Δ  k ≠ Δ, Δ±1 and all colors less than k adjacent to c. k=Δ+2 T1 2⩽k<Δ-1 T 2 0⩽k′<k-1<Δ-3 T 3 0 ⩽ k < k ′ - 1 < Δ - 2  c = Δ + 2  0 ⩽ k < Δ - 1 and all colors less than k adjacent to c. T1 2 ⩽ k < Δ - 1 or k=Δ T 2 c ≠ k ′ and 0⩽k′<k-1<Δ-2 or k=k′+2=Δ T 3 c ≠ k ′ and 0⩽k<k′-1<Δ-2 or 0⩽k⩽Δ-2 and k′=ΔTheorem 4.
If T is a tree withHλ(T)=1, then there exist infinitely many trees containing T and with maximum number of holes at least 1.Proof.
Here, we start with a one-hole irreducibleL(2,1)-span coloring of T having hole h. The construction of infinitely many trees is similar to that in Theorem 3 and using Table 4. Since after every step we get a tree T′ with one-hole irreducible span coloring, Hλ(T′)⩾1.Table 4
Trees connectable for a vertex coloredc in a one-hole tree with hole h.
Color of vertex Connectable trees Condition 0 ⩽ c < h  0 ⩽ k < h and all colors less than k adjacent to c. Forc=h-1, h<k⩽λ(T) and all colors less than k adjacent to c. c + 1 < k < h or k=h+1 k > h and all colors greater than h less than k adjacent to c. 2 ⩽ k < c - 1 k ′ ≠ c and 0<k<k′-1<h-1 or 0<k<h and k′=h+1 k ′ ≠ c and 0⩽k′<k-1<h-1 k > h c ≠ h - 1, k>h and all colors greater than h less than k adjacent to c. k > h and all colors greater than h less than k adjacent to c.  h ⩽ c ⩽ λ ( T )  0 ⩽ k < h and all colors less than k adjacent to c. Forc=h+1, h<k⩽λ(T) and all colors less than k adjacent to c. k > h and all colors greater than h less than k adjacent to c and c>h. h < c < k - 1 T 1 2 ⩽ k < h or k=h+1 T 2 0 < k < k ′ - 1 < h - 1 or 0<k<h and k′=h+1 T 3 0 ⩽ k ′ < k - 1 < h - 1 T 4 h + 2 < k < c - 1 T 5 k > h and all colors greater than h less than k adjacent to c. T 6 c ≠ h + 1, k>h and all colors greater than h less than k adjacent to c.Theorem 5.
IfT is a tree with Hλ(T)=1 and T has no two-hole span coloring, then there exist infinitely many trees with maximum number of holes one and containing T.Proof.
SinceT has no two-hole span coloring, any tree containing T having same maximum degree as that of T cannot have a two-hole span coloring. Therefore, every tree obtained from T using Theorem 4 has maximum number of holes one.Corollary 6.
IfT is a Type-I tree and Hλ(T)=1, then there exist infinitely many trees with maximum number of holes one and containing T.


## 3. Maximum Number of Holes in Some Type-II Trees

Recall that, in a graphG with maximum degree Δ, we refer a vertex v as a major vertex if its degree is Δ. Otherwise v is a minor vertex. Wood and Jacob [5] have given some sufficient conditions for a tree to be Type-II. We consider some of their sufficient conditions as below.Theorem 7 (see [5]).
A tree containing any of the following subtrees is Type-II provided the maximum degrees of the subtree and the tree are the sameΔ.(I)
T1: a tree with an induced P3 consisting of three major vertices.(II)
T2: a tree with a minor vertex w and at least 3 major vertices adjacent to w.(III)
T3: a tree with a major vertex w and at least Δ-1 major vertices at distance two from w, and T2 is not a subtree of the tree.(IV)
T4: a tree with a vertex w adjacent to Δ-2 vertices w1,w2,…,wΔ-2 and two neighbors vi,vi′ of each wi, 1⩽i⩽Δ-2 are major.Since the above trees can be as small as possible, we consider the degrees of minor vertices as minimum as possible. Now, we find the maximum number of holes for the treesT1,T2,T3, and T4. For any tree T with maximum degree Δ, it is clear that Hλ(T)⩽2. First, we show that Hλ(Ti)⩽1, i=1,2,4. Also, Hλ(T2)=0 if T2 has a vertex adjacent to at least four major vertices. Further, we give a two-hole L(2,1)-irreducible span coloring of T3 if it has exactly Δ-1 major vertices at distance two from a major vertex and we show that Hλ(T3)⩽1, if T3 has exactly Δ major vertices at distance two from a major vertex. Later, we show that these upper bounds are the exact values by defining L(2,1)-irreducible span colorings with appropriate holes. Now onwards, unless we mention, tree refers to Type-II tree. In figures, we use symbol ▲ to denote a major vertex.Theorem 8.
For the treesTi, i=1,2,4, Hλ(Ti)⩽1.Proof.
Letv1,v2, and v3 be the major vertices of T1. Since v1,v2, and v3 receive three different colors in any L(2,1)-coloring, by Lemma 1, T1 cannot have a two-hole irreducible span coloring. Similarly, we can prove that Hλ(T2)⩽1.
Now, we considerT4 with labelling as in Figure 1.
Suppose thatf is a two-hole irreducible span coloring of T4. Then by Lemma 1, all major vertices of T4 receive colors from {0,2} or {0,Δ+2} or {Δ,Δ+2}. Suppose the major vertices receive 0 and 2. Then 1 and 3 are holes. Without loss of generality, we assume that f(vi)=0 and f(vi′)=2. Now, one of the pendant vertices adjacent to vi must receive a color grater than 3 which reduces to 3 giving a contradiction to the fact that f is irreducible. Similarly, we can prove the other two cases. Therefore, Hλ(T4)⩽1.Figure 1
The treeT4 as in Theorem 7.Theorem 9.
If at least four major vertices are adjacent tow in T2, then Hλ(T2)=0.Proof.
Recall thatT2 is a tree with a vertex w adjacent to at least three major vertices. Let v1,v2,v3, and v4 be four major vertices adjacent to w in T2. Suppose that it has a one-hole irreducible L(2,1)-span coloring f. Let l1,l2,l3, and l4 be the colors received by v1,v2,v3, and v4, respectively. Without loss of generality, we assume that 0⩽l1<l2<l3<l4⩽Δ+2. If l1≠0, then except l1-1 and l1+1 all other colors are used to the neighbors of v1. Also, except l3-1 and l3+1, all other colors are used to the neighbors of v3. Since l1-1,l1+1,l3-1, and l3+1 are four different colors, f cannot have a hole which is a contradiction. So, l1=0. Since f is one-hole coloring, the colors l2-1,l2+1,l3-1, and l3+1 cannot be four different colors and hence l2+1=l3-1 is the hole. Now, a pendant neighbor of v1 receives l3 which reduces to the hole l3-1 giving a contradiction to the fact that f is irreducible.S. R. Kola et al. [10] have disproved the conjecture given by Laskar and Eyabi [9] by giving two-hole irreducible span colorings for Type-II trees of maximum degrees three and four. Following theorem gives a two-hole irreducible span coloring for a tree with maximum degree Δ which is also a counterexample for the conjecture.Theorem 10.
If exactlyΔ-1 major vertices are at distance two from the major vertex w in T3, then Hλ(T3)=2.Proof.
LetT3′ be the tree T3 with exactly Δ-1 major vertices at distance two to w. It is easy to see that the L(2,1)-span coloring of the tree T3′ given in Figure 2 is irreducible with 1 and 3 as holes.Figure 2
IrreducibleL(2,1)-span coloring of T3 with 1 and 3 as holes.Theorem 11.
IfT3′′ is the tree T3 with exactly Δ major vertices at distance two to w, then Hλ(T3′′)⩽1.Proof.
We considerT3′′ with labelling as in Figure 3.
Suppose thatT3′′ has an L(2,1)-span coloring f with two holes. Then by Lemma 1, all major vertices of T3′′ receive colors from {0,2} or {0,Δ+2} or {Δ,Δ+2}. Suppose that f assigns 0 and 2 to the major vertices. Since {f(w),f(vi)}={0,2}, 1⩽i⩽Δ, it is not possible to color all wi s as the four colors 0, 1, 2, and 3 cannot be assigned. Therefore, in this case, two-hole span coloring is not possible for T3′′. Similarly, we can prove the other two cases. Hence, Hλ(T3′′)⩽1.Figure 3
The treeT3 with exactly Δ major vertices at distance two to w.LetT2′ be the tree T2 with exactly three major vertices are adjacent to a vertex.Theorem 12.
For the treesT1, T2′, T3′′, and T4, the maximum number of holes is one.Proof.
It is easy to see that the colorings ofT1, T2′, T3′′, and T4 given in Figures 4, 5, 6, and 7, respectively, are irreducible L(2,1)-span colorings with hole Δ.Figure 4
IrreducibleL(2,1)-span coloring of T1 with one hole.Figure 5
IrreducibleL(2,1)-span coloring of T2′ with one hole.Figure 6
IrreducibleL(2,1)-span coloring of T3′′ with one hole.Figure 7
IrreducibleL(2,1)-span coloring of T4 with one hole.


## 4. Infinitely Many Trees with Holes 0, 1, and 2

Recall thatT2′ is the tree T2 with exactly three major vertices adjacent to a vertex and T3′′ is the tree T3 with exactly Δ major vertices at distance two from a major vertex. Let T2′′ be the tree T2 with exactly four major vertices adjacent to the vertex w. In this section, we give a sufficient condition for a Type-II tree to be a zero-hole tree. Also, we construct infinitely many trees with maximum number of holes 1 from each of the trees T1, T2′, T2′′, T3′′, and T4 and infinitely many two-hole trees containing T3′.Theorem 13.
If the treeT2 with at least five major vertices is a subtree of a tree T with maximum degree same as that of T2, then Hλ(T)=0.Proof.
Letv1,v2,v3,v4, and v5 be five major vertices adjacent to w and receive the colors l1,l2,l3,l4, and l5, respectively, by a one-hole span coloring f of T2. Without loss of generality, we assume that 0⩽l1<l2<l3<l4<l5⩽Δ+2. As in the proof of Theorem 9, we get l1=0 and l2+1=l3-1 is the hole. Since l4<l5⩽Δ+2, we have l4≠Δ+2. Since l4>l3, l3-1 must be used to a neighbor of v4 which is a contradiction. So, any L(2,1)-span coloring of T2 with at least five major vertices is a no-hole coloring. Therefore, if a tree T contains T2 with at least five major vertices and with maximum degree same as that of T2, then Hλ(T)=0.Theorem 14.
There are infinitely many trees with maximum number of holes one and containing each of the treesT1, T2′, T2′′, T3′′, and T4.Proof.
First, we prove thatT1, T2′, T2′′, T3′′, and T4 cannot have two-hole span coloring. From Theorems 8 and 11, it is clear that T1, T2′, T2′′, and T3′′ cannot have two-hole span colorings.
Next, we prove thatT4 cannot have a two-hole span coloring. We consider T4 with the labelling as in Theorem 12. Suppose that T4 has an L(2,1)-span coloring f with two holes. By Lemma 1, any major vertex of T4 receives the color from {0,2}, {0,Δ+2}, or {Δ,Δ+2}. Suppose f assigns 0 and 2 to major vertices. Then 1 and 3 are holes, {f(vi),f(vi′)}={0,2}, and wi cannot receive the colors 0,1,2, and 3. Therefore wis receive Δ-2 different colors among 4,5,6,…,Δ+2 (Δ-1 in number) and so, one of these colors is not used, say c. Since either c-1 or c+1 (if c=Δ+2 then c-1) is used to color one of the wis, c cannot be used to w. Since 1 and 3 are holes, there is no color for w. Similarly, we can prove the other cases.
Now, to use Theorem4, we need one-hole irreducible span coloring of T1, T2′, T2′′, T3′′, and T4. Since Hλ(T2′′) is 0, first we construct a tree T2′′′ from T2′′ such that Hλ(T2′′′)=1. We define a one-hole span coloring for T2′′ as in Figure 8 (T2′′ is a subtree of T2′′′). Since the colors Δ+1 and Δ+2 received by the vertices adjacent to the vertex u are reducible and there is no other color reducible, we connect star K1,Δ-2 to the vertices to make the colors Δ+1 and Δ+2 irreducible. The tree obtained is T2′′′.
Now, using Table5 obtained from Table 4 corresponding to the hole h=Δ and using irreducible one-hole span colorings of T1, T2′, T3′′, and T4 given in Theorem 12, we construct infinitely many one-hole trees containing each of the trees T1, T2′, T3′′, and T4, respectively. We get infinitely many trees containing T2′′ by using irreducible one-hole coloring of T2′′′ given in Figure 8 and using Table 5.Table 5
Trees connectable for a vertex coloredc in a one-hole tree with Δ as the hole.
Color of vertex Connectable trees Condition 0 ⩽ c < Δ  0 ⩽ k < Δ and all colors less than k adjacent to c. Forc=Δ-1, Δ<k⩽Δ+2 and all colors less than k adjacent to c. 2 ⩽ k < c - 1 k ′ ≠ c and 0<k<k′-1<Δ-1 or 0<k<Δ and k′=Δ+1 k = Δ + 1 k = Δ + 2 and Δ+1 is adjacent to c.  k ′ ≠ c and 0⩽k′<k-1<Δ-1 or k=Δ+1 and k′=Δ-1  k = Δ + 1 k = Δ + 2 and Δ+1 is adjacent to c.  c + 1 < k < Δ or k=Δ+1  c = Δ + 1, Δ+2  0 ⩽ k < Δ and all colors less than k adjacent to c. T 1 2 ⩽ k < Δ T 2 0 < k < k ′ - 1 < Δ - 1 or 0<k<Δ and k′=Δ+1 T 3 0 ⩽ k ′ < k - 1 < Δ - 1Figure 8
IrreducibleL(2,1)-span coloring of T2′′′ with Δ as hole.Example 15.
In Figure9, we illustrate the construction of one-hole tree as in Theorem 14 for the tree T1 with maximum degree Δ=7. The vertex b1 in T1 has color 4 and its neighbor’s color is 8. In Table 5, among the trees corresponding to the color c=4, the pendant vertex colored 0 is connected first. Later, pendant vertices colored 1 and 2 are connected, respectively. Similarly, some trees are connected to the vertices b2, b3, and di, 1⩽i⩽3.Figure 9
A tree with maximum number of holes one constructed fromT1.Theorem 16.
There are infinitely many trees containingT3′ and with maximum number of holes two.Proof.
The construction of trees is similar to the construction described in Theorem3. For the construction, we use two-hole irreducible span coloring of T3′ given in Figure 2 and Table 3.



---

*Source: 8186345-2018-09-20.xml*