A survey of Nordhaus-Gaddum type relations

Mustapha Aouchiche, Pierre Hansen

Research output: Contribution to journalArticlepeer-review

121 Citations (Scopus)

Abstract

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
Volume161
Issue number4-5
DOIs
Publication statusPublished - Mar 2013
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

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

Cite this