Nordhaus-Gaddum for Treewidth

Details Nordhaus-Gaddum for Treewidth Nordhaus-Gaddum for Treewidth

2011-09-07

arxiv.org/abs/1109.1602v1

European Journal of Combinatorics, 33/4:488--490, 2012

Mathematics

Combinatorics

Scientific paper

10.1016/j.ejc.2011.10.005

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.

Affiliated with

Also associated with

No associations

Rating

Nordhaus-Gaddum for Treewidth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nordhaus-Gaddum for Treewidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nordhaus-Gaddum for Treewidth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-474381