0
$\begingroup$

For treewidth $3$, there are four forbidden minors: K5, the graph of the octahedron, the pentagonal prism graph, and the Wagner graph.

This implies that the Wagner graph should have tree-width at least $4$ (since it is a minor of itself).

A graph has a bramble of order k if and only if it has treewidth at least $k − 1$. So the Wagner graph should have a bramble of order $5$.

However, I am struggling to construct such a bramble, nor can I find a paper that provides it to my satisfaction. Could someone please draw me a picture, or even provide a textual representation of a bramble with its corresponding hitting set for the Wagner graph? Or else, explain if I've made a mistake in my understanding?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Let's denote the vertices of the Wagner graph by $0,\dots, 7$ with edges from $i$ to $i+1 \mod 8$ and from $i$ to $i+4 \mod 8$. If i didn't overlook something, then $(0,1), (1,2), \dots, (6,7),(7,0)$ together with $(0,4)$ and $(1,5)$ form a bramble. The only way to hit the first 8 edges with 4 vertices is to take all odd or all even numbers, but then we'd miss at least one of the last two. Hence a minimal hitting set must contain at least 5 vertices. $\endgroup$
    – Florian Lehner
    Commented Nov 14, 2023 at 21:56
  • $\begingroup$ Thank you, that works! $\endgroup$
    – Mark Chimes
    Commented Nov 15, 2023 at 15:56

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .