A survey of Nordhaus-Gaddum type relations

Mustapha Aouchiche; Pierre Hansen

doi:10.1016/j.dam.2011.12.018

A survey of Nordhaus-Gaddum type relations

Mustapha Aouchiche, Pierre Hansen

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	466-546
Number of pages	81
Journal	Discrete Applied Mathematics
Volume	161
Issue number	4-5
DOIs	https://doi.org/10.1016/j.dam.2011.12.018
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

Access to Document

10.1016/j.dam.2011.12.018

Cite this

@article{1a5c93eaf76d47eba8c47b3158f506e6,

title = "A survey of Nordhaus-Gaddum type relations",

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 = "Complement, Graph, Inequalities, Invariants, Nordhaus-Gaddum",

author = "Mustapha Aouchiche and Pierre Hansen",

year = "2013",

month = mar,

doi = "10.1016/j.dam.2011.12.018",

language = "English",

volume = "161",

pages = "466--546",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "4-5",

}

TY - JOUR

T1 - A survey of Nordhaus-Gaddum type relations

AU - Aouchiche, Mustapha

AU - Hansen, Pierre

PY - 2013/3

Y1 - 2013/3

N2 - 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.

AB - 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.

KW - Complement

KW - Graph

KW - Inequalities

KW - Invariants

KW - Nordhaus-Gaddum

UR - http://www.scopus.com/inward/record.url?scp=84873411649&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873411649&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2011.12.018

DO - 10.1016/j.dam.2011.12.018

M3 - Article

AN - SCOPUS:84873411649

SN - 0166-218X

VL - 161

SP - 466

EP - 546

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 4-5

ER -

A survey of Nordhaus-Gaddum type relations

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this