Skip to Content

Joyce Yang

Picture of Joyce Yang.

Thesis

Interval Graphs

Advisor
Nicholas J. Pippenger
Second Reader(s)
Arthur T. Benjamin

Abstract

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$.

Additional Materials

Poster