The interval number of dense graphs

József Balogh, Andres Pluhár

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)423-429
Number of pages7
JournalDiscrete Mathematics
Issue number1-2
StatePublished - Sep 28 2002
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The interval number of dense graphs'. Together they form a unique fingerprint.

Cite this