
doi: 10.1137/0601001
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.
Extremal problems in graph theory, interval number, maximum degree, collection of finite closed intervals, interval graphs, 510, 004
Extremal problems in graph theory, interval number, maximum degree, collection of finite closed intervals, interval graphs, 510, 004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 64 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
