What are some good bounds on the Forbidden minors of the Torus?

312 Views Asked by At

What are some good bounds on the Forbidden minors of the Torus? By bounds I mean two sets of minors. One of which is such that having ANY of the graphs as minors means a graph is not Toroidal, and the other is such that having none of the graphs as minors will guarantee that the graph is Toroidal.

For example (K8 K3,7 K4,5) and (K3,3 K5) Is a possible example, the first set being made up of Graphs which are not Torodial, and the second being the Forbidden Minors of the plane. Though this is not a very tight bound.

Can anyone give a much better bound?

1

There are 1 best solutions below

0
On BEST ANSWER

One of your bounds is improved in in the paper "Forbidden minors and subdivisions for toroidal graphs with no $K_{3,3}$'s" by Gagarin, Myrvold, and Chambers.

It says that a graph with no $K_{3,3}$ minor is toroidal if and only if it does not contain the following four graphs as a minor:

enter image description here

In particular, having none of $\{K_{3,3}, G_1, G_2, G_3, G_4\}$ as a minor guarantees that a graph is toroidal.

Also, these graphs themselves have no $K_{3,3}$ minors. (We can check this, but it also follows from the authors wanting to state the shortest result possible.) So the theorem guarantees that they are individually not toroidal, and we can take $\{G_1, G_2, G_3, G_4\}$ as the other bound. I don't know how that compares to $\{K_8, K_{3,7}, K_{4,5}\}$, but it does mean that we have two similar looking bounds with "a gap of $K_{3,3}$ between them".

For that matter, we can take $\{K_8, K_{3,7}, K_{4,5}, G_1, G_2, G_3, G_4\}$ to guarantee an improvement on what you've got.