Graduation Year

2016

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Reader 1

Nicholas Pippenger

Reader 2

Arthur Benjamin

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2016 Joyce C Yang

Abstract

We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. 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 ω -2, where ω 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 ω -1.

Source Fulltext

math.hmc.edu/~jcyang/thesis/jcyang-2016-thesis.pdf

Download

Share

COinS