Extremal Values of the Interval Number of a Graph
Authors:
- Jerrold R. GriggsJGJerrold R. Griggs
- Douglas B. WestDWDouglas B. West
- 1 March 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 1 (1) , 1-7
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.
Keywords
This publication has 9 references indexed in Scilit:
- Extremal values of the interval number of a graph, IIDiscrete Mathematics, 1979
- On double and multiple interval graphsJournal of Graph Theory, 1979
- Graph Theory and Its Applications to Problems of Society1978
- Matrix characterizations of circular-arc graphsPacific Journal of Mathematics, 1971
- Characterizing circular-arc graphsBulletin of the American Mathematical Society, 1970
- Scheduling of traffic lights—A new approachTransportation Research, 1968
- Incidence matrices and interval graphsPacific Journal of Mathematics, 1965
- A Characterization of Comparability Graphs and of Interval GraphsCanadian Journal of Mathematics, 1964
- Representation of a finite graph by a set of intervals on the real lineFundamenta Mathematicae, 1962