On the Interval Number of a Triangulated Graph
Thomas Andreae · Journal of Graph Theory · 1987
Abstract 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) > m1/2.