A sharp edge bound on the interval number of a graph

József Balogh, András 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 intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Namely, it is shown that i(G) ≤ ⌈√e/2⌉ + 1. It is also observed that the edge bound induces i(G) ≤ √3γ(G)/2 + O(1), where γ(G) is the genus of G.

Original languageEnglish (US)
Pages (from-to)153-159
Number of pages7
JournalJournal of Graph Theory
Issue number2
StatePublished - Oct 1999
Externally publishedYes


  • Density
  • Griggs-West conjecture
  • Interval number

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'A sharp edge bound on the interval number of a graph'. Together they form a unique fingerprint.

Cite this