Extremal values of the interval number of a graph

Abstract. The interval number i(G) of a simple graph G is the smallest number such that to each vertex in G there can be assigned a collection of at most 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)=<I. We prove here that for any graph G with maximum degree d, i(G) <- [1/2(d + 1)]. 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) <- [1/2n] for graphs on n vertices and i(G)<- [/J for graphs with e edges. 1. Introduction to interval numbers. We begin by discussing earlier work on interval graphs and boxicity in order to motivate the definition of interval numbers. A simple bound on the interval number given the numbers of edges and of vertices of a graph is presented along with results on the interval number of some basic graphs. In the next section we prove our main result, which gives the best-possible upper bound on th