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.
|Number of pages||81|
|Journal||Discrete Applied Mathematics|
|Publication status||Published - Mar 2013|
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics