Skip to main content
MathOverflow

Return to Question

removed capitals from title
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Bramble with Orderorder 5 for the Wagner Graphgraph

For treewidth 3$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 $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$k − 1$. So the Wagner graph should have a bramble of order 5$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?

Bramble with Order 5 for the Wagner Graph

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?

Bramble with order 5 for the Wagner graph

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?

Source Link
Mark Chimes
Mark Chimes
  • 101
  • 1

Bramble with Order 5 for the Wagner Graph

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?