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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:GRIsiamjadm80

## Abstract

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.

Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/0601001DOIUNSPECIFIED
Additional Information:© 1980 Society for Industrial and Applied Mathematics. Received 22 January 1979. We are indebted to Fred Roberts for introducing us to interval graphs and for bringing the work of Trotter and Harary to our attention; to Robert McGuigan for proposing the study of interval numbers; and to Daniel J. Kleitman for making some valuable suggestions. This work originated at the NSF-CBMS Regional Conference in Graph Theory at Colby College, June, 1977.