Campus Units

Mathematics

Document Type

Book Chapter

Publication Version

Accepted Manuscript

Publication Date

2016

Journal or Book Title

Recent Trends in Combinatorics

Volume

159

First Page

275

Last Page

294

DOI

10.1007/978-3-319-24298-9_12

Abstract

A Nordhaus-Gaddum problem for a graph parameter is to determine a tight lower or upper bound for the sum or product of the parameter evaluated on a graph and on its complement. This article surveys Nordhaus-Gaddum results for the Colin de Verdiere type parameters mu, nu, and xi; tree-width and its variants largeur d'arborescence, path-width, and proper path-width; and minor monotone ceilings of vertex connectivity and minimum degree.

Comments

This is a post-peer-review, pre-copyedit version of a book chapter published as Hogben, Leslie. "Nordhaus-Gaddum problems for Colin de Verdiere type parameters, variants of tree-width, and related parameters." In Beveridge A., Griggs J., Hogben L., Musiker G., Tetali P. (eds) Recent Trends in Combinatorics. The IMA Volumes in Mathematics and its Applications, vol. 159. Springer, Cham. (2016): 275-294. DOI: 10.1007/978-3-319-24298-9_12. Posted with permission.

Copyright Owner

Springer International Publishing Switzerland

Language

en

File Format

application/pdf

Published Version

Share

COinS