17
$\begingroup$

This question is similar to one 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 for more details.

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

$\endgroup$
  • $\begingroup$ In the first question, with "forbidden minor" you mean "minimal forbidden minor", don't you? if not the grid graphs are an example. $\endgroup$ – Diego de Estrada Nov 17 '11 at 19:11
  • 1
    $\begingroup$ Yes. I meant minimal forbidden minor. $\endgroup$ – Shiva Kintali Nov 17 '11 at 19:13
  • 2
    $\begingroup$ 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. $\endgroup$ – joriki Nov 18 '11 at 7:53
  • $\begingroup$ @joriki I updated the question. $\endgroup$ – Shiva Kintali Nov 18 '11 at 15:18
9
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Yes. Lets exclude grid graphs. $\endgroup$ – Shiva Kintali Nov 17 '11 at 20:07
13
$\begingroup$

In Sparse obstructions and exact treewidth determination, Lucena states that in the PhD thesis of Sanders, "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."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.