On the Interval Number of a Triangulated Graph

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices v and w of G are adjacent if and only if some interval for v intersects some interval for w. For triangulated graphs G, we consider the problem of finding a sharp upper bound for the interval number of G in terms of its clique number ω(G). The following partial results are proved. (1) For each triangulated graph G, i(G) ? ?ω(G)/2? + 1, and this is best possible for 2 ? ω(G) ? 6. (2) For each integer m ? 2, there exists a triangulated graph G with ω(G) = m and i(G) > m^1/2.