On the interval number of special graphs

József Balogh, Pascal Ochem, András Pluhár

Research output: Contribution to journalArticlepeer-review


The interval number of a graph 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 intervals, denoted by i(G). Griggs and West showed that i(G) ≤ [1/2(d + 1)]. We describe the extremal graphs for that inequality when dis even. For three special perfect graph classes we give bounds on the interval number in terms of the independence number. Finally, we show that a graph needs to contain large complete bipartite induced subgraphs in order to have interval number larger than the random graph on the same number of vertices.

Original languageEnglish (US)
Pages (from-to)241-253
Number of pages13
JournalJournal of Graph Theory
Issue number4
StatePublished - Aug 2004
Externally publishedYes


  • Graph representation
  • Interval number

ASJC Scopus subject areas

  • Geometry and Topology


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

Cite this