The interval number of dense graphs

AbstractThe interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t closed intervals. Most known bounds on i(G) are grossly excessive when G has more than half of the possible edges. A plausible remedy is to develop bounds on i(G) that are monotone decreasing in G. Here we bound i(G) in terms of e(Ḡ), the number of edges in the complement of G. We prove that i(G)⩽⌈12e(Ḡ)⌉+O(n/logn).