Extremal Values of the Interval Number of a Graph
- Creators
- Griggs, Jerrold R.
- West, Douglas B.
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.
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.Attached Files
Published - GRIsiamjadm80.pdf
Files
Name | Size | Download all |
---|---|---|
md5:9227689511c84b420c0fceedadd5383a
|
806.2 kB | Preview Download |
Additional details
- Eprint ID
- 12785
- Resolver ID
- CaltechAUTHORS:GRIsiamjadm80
- Created
-
2008-12-23Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field