Nordhaus-Gaddum for treewidth

DOI10.1016/J.EJC.2011.10.005zbMATH Open1239.05151arXiv1109.1602OpenAlexW2039737021MaRDI QIDQ412239FDOQ412239

Gwenaël Joret, David R. Wood

Publication date: 4 May 2012

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

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.

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

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Graph searching and a min-max theorem for tree-width
• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• On Complementary Graphs
• Clique minors in graphs and their complements
• Nordhaus–Gaddum‐type Theorems for decompositions into many parts
• On Hadwiger's number---A problem of the Nordhaus-Gaddum type
• On the Hajós number of graphs
• Rank-width of random graphs
• Title not available (Why is that?)
• Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting
• Title not available (Why is that?)

Cited In (2)

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

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)