I i5 showll that the interval number of a gralh on n vertices is a~ inosl [I;(n ~ Ij], md this bound is best possible. This means that we can represent any l~raph ,,n n verl~cc~ as an intersection graph in which the sets ~ssigued Io the verUccs each ~or, sist of tlxe umorl ~a at m~st [~(n + I)] finite closed intervals on the real I ne Thi,Β’ upper boul,d is .iialned by the clmlf~]ele bipartite graph Kl,,,2j3,,,21. Interval grapb~ have been studied exl:ensively ~or lnore than fifteen years and .":ave been shown to have a wide variety of applications [ 1.2, 4, 5]..atervai graphs are simple: undirected graphs (7 with the property that the>: exisls a collection of finite closed intervals o!1 the real line, one interval /,, = [a~, "o] assigned to each vertex v in G, sach that two vert ces v amt w arc joined b 5 an edg~ in G ii al:d only if 1~, intersects I~. Trotter and h=r'ary [7 a and, independently, McGuigar~, Griggs anti West [3.6] have extended this idea of repres,:nting graphs by the intersections of intervals.
represent each vertex v in G J~y a collection of t finite closed intervals 1~,,. I~,2 ..... 1~,., in such a way tha: ~wo vertices t~ and w are joined by an edge i,, G if and only if some interval I~, i intersects some int,.'rval t~,r [:or a given grui% G, we dafine the interval number of G, denoted i(G}, to be the sm~,liest integer t~(I for which such a representatiorl of G is pos~;ibte, For every graph G, :(G) ~ well-defined. Interval graphs are precisely those graphs f; with i(G,-"~ I.
By assigning the ~ame interval to each verter:, wc find that ~(E,,t=~ 1. It :,, consid~:rably more difficult ~'o derive tile interval numbers for complete bipartite graphs. However, Trotter and Harary discovered an elegant interval construc'~.m which proved tae following: ~'l~eorem I. .. I-am+ lq ,Β’K.,.,a =/7~1 If G either has very many edges, as in a complete graph, or very fe.v ed.es, as in a simple path, then i(G) can he as small as 1. But how large can i, G) Bet? It carl ~et arbitrarily large, for i(K...} = [Β½(n Γ· 1)], b3, Theorern 1. But ~Β’ we restrict