CaltechAUTHORS
A Caltech Library Service

# Extremal Values of the Interval Number of a Graph

Griggs, Jerrold R. and West, Douglas B. (1980) Extremal Values of the Interval Number of a Graph. SIAM Journal on Algebraic and Discrete Methods, 1 (1). pp. 1-7. ISSN 0196-5212 http://resolver.caltech.edu/CaltechAUTHORS:GRIsiamjadm80

 Preview
PDF - Published Version
See Usage Policy.

787Kb

The interval number $i( G )$ of a simple graph $G$ is the smallest number $t$ such that to each vertex in $G$ there can be assigned a collection of at most $t$ finite closed intervals on the real line so that there is an edge between vertices $v$ and $w$ in $G$ if and only if some interval for $v$ intersects some interval for $w$. The well known interval graphs are precisely those graphs $G$ with $i ( G )\leqq 1$. We prove here that for any graph $G$ with maximum degree $d, i ( G )\leqq \lceil \frac{1}{2} ( d + 1 ) \rceil$. This bound is attained by every regular graph of degree $d$ with no triangles, so is best possible. The degree bound is applied to show that $i ( G )\leqq \lceil \frac{1}{3}n \rceil$ for graphs on $n$ vertices and $i ( G )\leqq \lfloor \sqrt{e} \rfloor$ for graphs with $e$ edges.