# Treewidth of deep Sierpiński Sieve Graph

Note $$S_n$$ the Sierpiński sieve graph of order $$n$$, which is obtained from the connectivity of the Sierpiński sieve.

For $$n$$ high enough, what is the treewidth of $$S_n$$?

I think that I can show that it is at least $$4$$ (by obtaining $$K_5$$ as a graph minor), and that it is at most $$5$$ (by obtained a tree-decomposition scheme involving bags of size $$6$$). My gut feeling is that it should be $$5$$, but I cannot find a proper database for forbidden minors at treewidth $$4$$ (and I can't access Sanders' thesis mentioned here).

## 1 Answer

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width four.

There is no $K_5$ minor, because the graph is planar. There is, however, a $K_{2,2,2}$ (octahedron) minor (actually, a subdivision), shown below. As this is one of the forbidden minors for treewidth three, the width is four.

• Nice figure @David Eppstein. How did you draw it? – Chandra Chekuri Sep 6 '16 at 22:33
• Adobe Illustrator, mostly using their click, drag and snap copying operation to repeatedly triple a single equilateral triangle. – David Eppstein Sep 6 '16 at 22:47
• Thanks for the clear explanation! I should have realized that there can't be a $K_5$ since it is planar... – while False Sep 7 '16 at 0:44