A survey of Nordhaus-Gaddum type relations
A survey of Nordhaus-Gaddum type relations
复制标题
DOI：
10.1016/j.dam.2011.12.018
复制
发表时间：
2013-03-01
影响因子：
1.1
通讯作者：
Hansen, Pierre
中科院分区：
文献类型：
--
作者：
Aouchiche, Mustapha;Hansen, Pierre
1956年，诺德豪斯（Nordhaus）和加达姆（Gaddum）根据图的阶数，给出了一个图的色数及其补图的色数之和与积的上下界。从那时起，在数百篇论文中，针对许多其他图不变量也提出了类似类型的关系。我们对这一研究工作进行综述。© 2011爱思唯尔（Elsevier）出版集团。保留所有权利。
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. (C) 2011 Elsevier B.V. All rights reserved.