A sharp edge bound on the interval number of a graph

The interval number of a graph G, denoted by i(G), is the least natural num ber t such that G is the intersection graph of sets, each of which is the u nion of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Name ly, it is shown that i(G) less than or equal to inverted right perpendicula r root e/2 inverted left perpendicular + 1. It is also observed that the ed ge bound induces i(G) less than or equal to root 3 gamma(G)/2+O(1), where g amma(G) is the genus of G. (C) 1999 John Wiley & Sons, Inc. J Graph Theory 32: 153-??, 1999.