<p>In <a href="http://www1.aucegypt.edu/faculty/lucena/files/obstwdet.pdf">Sparse obstructions and exact treewidth determination</a>, Lucena states that in the <a href="http://smartech.gatech.edu/handle/1853/30061">PhD thesis of Sanders</a>, "75 or so minimal forbidden minors for treewidth $\leq 4$ are given, and it is believed though not proven that this may constitute the entire obstruction set."</p>

CC BY-SA 3.0
2011-11-17T22:43:45.087Z
2011-11-17T22:43:45.087Z
Aaron Sterling
<p>If G is formed from a smaller graph H that is not a clique by adding two vertices x and y, such that x and y are not adjacent to each other but adjacent to all other vertices of G, then $tw(G)=tw(H)+2$. For, in any tree decomposition of $G$, either $x$ and $y$ have disjoint subtrees or they have overlapping subtrees. If they have disjoint subtrees, all the other subtrees have to include the shortest path between the trees for $x$ and $y$, from which it follows that the treewidth is $n-2$; the assumption that $H$ is not a clique can then be used to show that $n-2\ge tw(H)+2$. Alternatively if $x$ and $y$ have overlapping subtrees, every other vertex has to have a subtree that touches the intersection of the two subtrees of $x$ and $y$, and we can restrict the tree decomposition to that intersection, giving a tree decomposition in which $x$ and $y$ participate in every tree node.</p>

<p>This implies that the hyperoctahedral graph $K_{2,2,2,\dots}$ with $2k$ nodes is a minimal forbidden minor for width $2k-3$. For, the octahedral graph $K_{2,2,2}$ is a minimal forbidden minor for width three, from which the argument above shows that the hyperoctahedral graph has width $2k-2$. And if any edge contraction or edge deletion is performed in the hyperoctahedral graph, the symmetries of the graph allow us to assume that the operation is happening to one of the twelve edges in the base octahedron, causing its width and the width of all the hyperoctahedra built from it to decrease.</p>

<p>(The other class of graphs you should be including in your question along with the complete graphs are the grid graphs. An $r\times r$ grid has treewidth $r$. It's separate from the complete graph minors because its planar and therefore has no complete minor with more than four vertices. It's not a minimal forbidden minor, though, because some small changes (such as contracting the corner vertices) don't change its treewidth.)</p>

CC BY-SA 3.0
2011-11-17T20:07:38.810Z
Yes. Lets exclude grid graphs.
Shiva Kintali
CC BY-SA 3.0
2011-11-17T19:49:57.447Z
2011-11-17T23:23:04.603Z
2011-11-17T23:23:04.603Z
David Eppstein
<p>This question is similar to <a href="https://cstheory.stackexchange.com/questions/8876/forbidden-minors-for-bounded-genus-graphs">one</a> of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$. </p>

<blockquote>
  <p>Is there a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs and grid graphs) that are minimal forbidden minors for graphs of every treewidth. In other words, is there an explicit graph $G_r$ on $r$ vertices (which is not a complete graph) such that $G_r$ is a forbidden minor for graphs of treewidth at most $r$, where $r$ is a function of $t$ ?</p>
</blockquote>

<p>The complete sets of forbidden minors are known for graphs of treewidth at most three. See this <a href="http://en.wikipedia.org/wiki/Treewidth#Forbidden_minors" rel="nofollow noreferrer">Wikipedia article</a> for more details.</p>

<blockquote>
  <p>Is the complete set of forbidden minors of graphs of treewidth at most four known ?</p>
</blockquote>

CC BY-SA 3.0
2011-11-17T19:11:17.237Z
In the first question, with "forbidden minor" you mean "minimal forbidden minor", don't you? if not the grid graphs are an example.
didest
CC BY-SA 3.0
2011-11-17T19:13:12.993Z
Yes. I meant minimal forbidden minor.
Shiva Kintali
CC BY-SA 3.0
2011-11-18T07:53:22.763Z
You've made two comments augmenting your question, one here and one under an answer; it would be preferable to include the changes in the question itself so people don't have to read through various comment threads to understand the question.
joriki
CC BY-SA 3.0
2011-11-18T15:18:58.413Z
@joriki I updated the question.
Shiva Kintali
<graph-theory><co.combinatorics><treewidth><graph-minor>
Forbidden minors for bounded treewidth graphs
Shiva Kintali
# Forbidden minors for bounded treewidth graphs

(Asked by: username_0 on 2011-11-17)

This question is similar to [one](https://cstheory.stackexchange.com/questions/8876/forbidden-minors-for-bounded-genus-graphs) of my previous questions. It is known that $K\_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$.

> Is there a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs and grid graphs) that are minimal forbidden minors for graphs of every treewidth. In other words, is there an explicit graph $G\_r$ on $r$ vertices (which is not a complete graph) such that $G\_r$ is a forbidden minor for graphs of treewidth at most $r$, where $r$ is a function of $t$ ?

The complete sets of forbidden minors are known for graphs of treewidth at most three. See this [Wikipedia article](http://en.wikipedia.org/wiki/Treewidth#Forbidden_minors) for more details.

> Is the complete set of forbidden minors of graphs of treewidth at most four known ?

**Tags:** graph-theory, co.combinatorics, treewidth, graph-minor

> **Comments:**
> **username_1**: In the first question, with "forbidden minor" you mean "minimal forbidden minor", don't you? if not the grid graphs are an example.  
> **username_0**: Yes. I meant minimal forbidden minor.  
> **username_2**: You've made two comments augmenting your question, one here and one under an answer; it would be preferable to include the changes in the question itself so people don't have to read through various comment threads to understand the question.  
> **username_0**: @username_2 I updated the question.  

---

## 2 answers

### Answer by username_4 on 2011-11-17. Score: 9 | Accepted answer

If G is formed from a smaller graph H that is not a clique by adding two vertices x and y, such that x and y are not adjacent to each other but adjacent to all other vertices of G, then $tw(G)=tw(H)+2$. For, in any tree decomposition of $G$, either $x$ and $y$ have disjoint subtrees or they have overlapping subtrees. If they have disjoint subtrees, all the other subtrees have to include the shortest path between the trees for $x$ and $y$, from which it follows that the treewidth is $n-2$; the assumption that $H$ is not a clique can then be used to show that $n-2\ge tw(H)+2$. Alternatively if $x$ and $y$ have overlapping subtrees, every other vertex has to have a subtree that touches the intersection of the two subtrees of $x$ and $y$, and we can restrict the tree decomposition to that intersection, giving a tree decomposition in which $x$ and $y$ participate in every tree node.

This implies that the hyperoctahedral graph $K\_{2,2,2,\dots}$ with $2k$ nodes is a minimal forbidden minor for width $2k-3$. For, the octahedral graph $K\_{2,2,2}$ is a minimal forbidden minor for width three, from which the argument above shows that the hyperoctahedral graph has width $2k-2$. And if any edge contraction or edge deletion is performed in the hyperoctahedral graph, the symmetries of the graph allow us to assume that the operation is happening to one of the twelve edges in the base octahedron, causing its width and the width of all the hyperoctahedra built from it to decrease.

(The other class of graphs you should be including in your question along with the complete graphs are the grid graphs. An $r\times r$ grid has treewidth $r$. It's separate from the complete graph minors because its planar and therefore has no complete minor with more than four vertices. It's not a minimal forbidden minor, though, because some small changes (such as contracting the corner vertices) don't change its treewidth.)

> **Comments:**
> **username_0**: Yes. Lets exclude grid graphs.  

---

### Answer by username_3 on 2011-11-17. Score: 14

In [Sparse obstructions and exact treewidth determination](http://www1.aucegypt.edu/faculty/lucena/files/obstwdet.pdf), Lucena states that in the [PhD thesis of Sanders](http://smartech.gatech.edu/handle/1853/30061), "75 or so minimal forbidden minors for treewidth $\leq 4$ are given, and it is believed though not proven that this may constitute the entire obstruction set."


---

