An Upper Bound for the Depth-\(r\) Interval Number of the Complete Graph

A \(t\)-interval representation \(f\) of a graph \(G\) is a function which assigns to each vertex \(v \in V(G)\) a union of at most \(t\) closed intervals \(I_{v,1}, I_{v,2}, \ldots, I_{v,t}\) on the real line such that \(f(v) \cap f(w) \neq \emptyset\) if and only if \(v, w \in V(G)\) are adjacent. If no real number lies in more than \(r\) intervals of the representation, we say the interval representation has depth \(r\). The least positive integer \(t\) for which there exists a \(t\)-representation of depth \(r\) of \(G\) is called the depth-\(r\) interval number \(i_r(G)\). E. R. Scheinerman proved that \(i_2(K_n) = \lceil \frac{n}{2} \rceil\) for \(n \geq 2\) and that \(\lceil \frac{n-1}{2(r-1)}+\frac{r}{2n} \rceil \leq i_r(K_n) \leq \frac{n}{2r-2}+1+2\lceil log_r n \rceil \). In the following paper, we will see by construction that \(i_3(K_n) = \lceil \frac{n-1}{4}+\frac{3}{2n} \rceil \). If \(n \geq 5\), this is equal to \(\lceil \frac{n}{4} \rceil\). The main theorem is: if \(n \geq r \geq 4\), then \(i_r(K_n) \leq \max \{ \lceil \frac{n-2}{2(r-1)}+\frac{1}{2} \rceil , 2 \}\). The difference between the lower and upper bounds is at most \(1\).