The 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) ≤ [1/2√e(Ḡ)] + O(/z/logn).
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics