## 3 Upper Bounds on the Number of Channels
### Upper Bounds on the Number of Channels
Similarly, we draw other two lines in parallel with \(X_{i}X_{j}\) and the lower border of the interference region of \(X_{i}\). Those lines and the arc of the interference region of \(X_{j}\) form the region \(ABCDEFG\) with the bold border, as shown in Figure 5 (note that the length of \(CD\) is equal to the length of \(AG\), which is equal to the length of \(X_{k}X_{l}\)). Thus, those interfering nodes should all fall in this region. Then we illustrate that this region can be covered by three identical sectors with radius \(R_{i}=2\) and angle \(\theta_{m}\). We place these three sectors as follows. First, we put a sector with one of its edge tightly clinging to the thick line as shown in Figure 5. By calculating the coordinates of point \(A\) and point \(B\), we can prove that \(R_{i}\) is greater than segment \(AB\). Then we place the second sector next to the first one as shown in Figure 5. Similarly, we can prove that points \(C\) and \(D\) fall in the second sector by calculating  
Figure 4: The plane is divided into two parts. the coordinates of \(C\) and \(D\). Then we put the third sector next to the second one. Point \(E\) falls in the third sector. Points \(F\) and \(G\) also fall in the first sector. So, the region \(ABCDEFG\) can be covered by the three sectors. Since the region \(ABCDEFG\) can be covered by three identical sectors with radius \(R_{i}\) and angle \(\theta_{m}\), by definition of the node density, the number of nodes in region \(ABCDEFG\) is at most \(3D\). Those \(3D\) nodes can form at most \(\frac{3}{2}D\) links in this area. Other than link \(l_{ij}\), there are at most \(\frac{3}{2}D-1\) links that can interfere with link \(l_{ij}\). Therefore, every vertex in subgraph \(H\) (the gray area in Figure 5) of \(G\) has a vertex with degree at most \(\frac{3}{2}D-1\). From Lemma 2, the conflict graph can be colored by using \(\frac{3}{2}D\) colors. Note that the result of Theorem 2 also holds for any \(r>2\). More specifically, we have the following result. **Theorem 3**: _If an upper bound \(U\) is valid for the interference ratio \(r=r_{1}\), \(r_{1}\geq 2\) and \(r_{2}>r_{1}\), then the upper bound \(U\) is also valid for \(r=r_{2}\)._  
**Proof. ** Without loss of generality, we have the assumption that the interference range is fixed at \(R_{i}=1\) in both following two cases. Case I (\(r=r_{1}\)):  
The transmission range in this case \(R_{t1}=\frac{R_{i}}{r_{1}}=\frac{1}{r_{1}}\) and \(U\) is a valid upper bound. Case II (\(r=r_{2}\)):  
Thus, the transmission range in the second case \(R_{t2}=\frac{R_{i}}{r_{2}}=\frac{1}{r_{2}}\). Since \(r_{2}>r_{1}\), we have \(R_{t1}>R_{t2}\). This means that the transmission range \(R_{t1}\) in the first case (\(r=r_{1}\)) is larger than the transmission range \(R_{t2}\) in the second case (\(r=r_{2}\)). That is to say _any valid link set \(LS\) in the second case is also valid in the first case_. Since interference ranges are equal in the two cases, link set \(LS\) will result in the same conflict graph in the two cases. Recall the assumption that when \(r=r_{1}\), \(U\) colors are enough to satisfy \(G(LS)\). Therefore, \(U\) is also a valid upper bound when \(r=r_{2}\). As shown in Theorem 3, the upper bound is monotonically non-increasing as interference ratio \(r\) increases. Intuitively, the larger the interference ratio \(r\) is, the further reduced the upper bound \(U\) can be. When \(r=4\), we have the following result. Figure 5: The proof of Theorem 2. **Theorem 4**: _When \(r=4\) and \(n\) nodes are distributed in a planar area with density \(D\), and each node is equipped with an antenna with beamwidth \(\theta_{m}\), for any valid link set \(LS\) derived from those \(n\) nodes, the corresponding conflict graph \(G(LS)\) can be colored by using \(D\) colors._  
**Proof. ** We take the similar proof techniques to prove Theorem 4. Without loss of generality, we assume that \(R_{t}=1\) and \(R_{i}=4\). From Lemma 2, it is sufficient to prove that \(\delta(G)\leq D-1\).