Nordhaus-Gaddum for Treewidth

Abstract

We prove that for every graph $G$ with $n$ vertices, the treewidth of $G$ plus the treewidth of the complement of $G$ is at least $n-2$. This bound is tight.

References in corpus (1)

• On the tree-depth of Random Graphs

Cited by in corpus (1)

• Nordhaus-Gaddum bounds for locating domination