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. 17. ISSN 01965212. doi:10.1137/0601001. https://resolver.caltech.edu/CaltechAUTHORS:GRIsiamjadm80

PDF
 Published Version
See Usage Policy. 806kB 
Use this Persistent URL to link to this item: https://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: 
 
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 NSFCBMS Regional Conference in Graph Theory at Colby College, June, 1977.  
Issue or Number:  1  
DOI:  10.1137/0601001  
Record Number:  CaltechAUTHORS:GRIsiamjadm80  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:GRIsiamjadm80  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  12785  
Collection:  CaltechAUTHORS  
Deposited By:  Archive Administrator  
Deposited On:  23 Dec 2008 21:35  
Last Modified:  08 Nov 2021 22:33 
Repository Staff Only: item control page