- Nicholas J. Pippenger
- Second Reader(s)
- Arthur T. Benjamin
We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the generating function of $i_n$, the number of interval graphs on $n$ vertices, has a positive radius of convergence. We have found that it is zero. We have also found that the exponential generating function of $i_n$ has a radius of convergence greater than or equal to one half. We have obtained a lower bound and an upper bound on $i_n$.
We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The most colors used by Kierstead\'s algorithm is $3 \omega -2$, where $\omega$ is the size of the largest clique in the graph. We determine a lower bound on the colors used. One such lower bound is $2\omega-1$.