On the interval number of random graphs
Edward R. Scheinerman · Discrete Mathematics · 1990
Erdős and West [6] showed that for almost all graphs G (with edge probability 12), the interval number of G, denoted i(G), satisfies n⧸(4 lg n)⩽i(G)⩽(n + 1)⧸4. We improve their result by showing that for almost every graph, i(G)∼12(n⧸lg n).