Nordhaus-Gaddum for treewidth

DOI10.1016/J.EJC.2011.10.005MaRDI QIDQ412239zbMATH OpenOpenAlexFDO

Authors Gwenaël Joret, David R. Wood

Publication date 4 May 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.1602

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• Clique minors in graphs and their complements
• Graph searching and a min-max theorem for tree-width
• Graph theory
• scientific article; zbMATH DE number 3926948 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 4185642 (Why is no real title available?)
• Nordhaus–Gaddum‐type Theorems for decompositions into many parts
• On Complementary Graphs
• On Hadwiger's number---A problem of the Nordhaus-Gaddum type
• On the Hajós number of graphs
• Rainbow perfect matchings in complete bipartite graphs: existence and counting
• Rank-width of random graphs

Cited in

(3)

• Nordhaus-Gaddum bounds for locating domination
• Nordhaus-Gaddum type bounds for the complement rank
• Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph

This page was built for publication: Nordhaus-Gaddum for treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412239)