Article ID Journal Published Year Pages File Type
420029 Discrete Applied Mathematics 2013 81 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A survey of Nordhaus–Gaddum type relations
Authors
, ,