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 language | English |
---|---|
Pages (from-to) | 466-546 |
Number of pages | 81 |
Journal | Discrete Applied Mathematics |
Volume | 161 |
Issue number | 4-5 |
DOIs | |
Publication status | Published - Mar 2013 |
Externally published | Yes |
Keywords
- Complement
- Graph
- Inequalities
- Invariants
- Nordhaus-Gaddum
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics