Forbidden minors of a graph with treewidth at most 4

Question

I am interested in the graphs with treewidth 5 because of their relationship with the realization dimension of a graph (see here).

In this PhD thesis, 75 minimal forbidden minors of graphs with treewidth at most four are given.

Unfortunately, I don't have access to the above thesis. Does anyone know some or a complete list of them (other than $K_6$)?

Or, is there any easy example (not necessarily minimal) of a graph with treewidth 5? I know that $K_6$ and the $5 \times 5$ grid graph have this property.

Answer 1

I have a copy of Sander's PhD thesis. Counting $K_6$, there are actually $76$ excluded minors for treewidth at most $4$ (found by computer) in the thesis, but it is unknown if this list is complete (it is complete up to $8$ vertices). The $76$ graphs are too sporadic to describe here, but send me an email if you want to know more.

Regarding the connection to realization dimension, Samuel Fiorini, Gwenaël Joret, Carole Muller and I proved that realization dimension and treewidth are essentially the same thing (see here). By essentially the same thing I mean that each is bounded as a function of the other. Since realization dimension is a minor-monotone property, another way to phrase our result is that a minor-closed class of graphs has bounded realization dimension if and only if it has bounded treewidth. Alternatively, by the Grid Theorem, a minor-closed class has unbounded realization dimension if and only if it contains all planar graphs.

By the Graph Minor Theorem of Robertson and Seymour, for each fixed $k$, the property of having realization dimension at most $k$ can be characterized by a finite set of excluded minors. Belk and Connelly (in the article you link to) proved that a graph has realization dimension at most $3$ if and only if it does not have $K_5$ or $K_{2,2,2}$ as a minor. There are also versions of realization dimension for other metric spaces (most notably $\ell_\infty$), and the excluded minors for $\ell_\infty$-dimension at most $2$ were found here. In her Master's thesis, Carole Muller found many excluded minors for $\ell_\infty$-dimension at most $3$. The thesis is not publicly available, but I have an electronic copy if you're interested.

Answer 2

This is not a complete solution in the sense of a complete list, just a description to get an easy example of a graph of treewidth $5$ that does not have $K_6$ as a minor.

As far as I know, the general structure of graphs without $K_6$ as a minor does not have an easy description (although partial results are known i.e. for large $6$-connected graphs see arXiv:1203.2192).

However, the structure of graphs without $K_5$ as a minor is known and due to Wagner, see for example https://en.wikipedia.org/wiki/Wagner%27s_theorem. Briefly, any such graph is a clique-sum (over cliques of size at most $3$) of planar graphs and a special graph on eight vertices, the so-called Wagner graph $W$. This graph is known to be one of the four minimal forbidden minors for graphs of treewidth at most $3$, see for example https://en.wikipedia.org/wiki/Wagner_graph. Hence, $W$ has treewidth $4$.

Now by taking $W$ and adding an apex vertex, i.e., a vertex that is adjacent to every vertex of $W$, you get a graph that now does not contain $K_6$ as a minor and whose treewidth is $5$.