A survey of Nordhaus-Gaddum type relations

Mustapha Aouchiche, Pierre Hansen

Research output: Contribution to journalArticlepeer-review

129 Citations (Scopus)


In 1956, Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement, in terms of the order of the graph. Since then, relations of a similar type have been proposed for many other graph invariants, in several hundred papers. We present a survey on this research endeavor.

Original languageEnglish
Pages (from-to)466-546
Number of pages81
JournalDiscrete Applied Mathematics
Issue number4-5
Publication statusPublished - Mar 2013
Externally publishedYes


  • Complement
  • Graph
  • Inequalities
  • Invariants
  • Nordhaus-Gaddum

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'A survey of Nordhaus-Gaddum type relations'. Together they form a unique fingerprint.

Cite this