Minor-closed classes of graphs with large numbers of excluded minors

Question

Robertson and Seymour tell us that any minor-closed family of graphs has a finite collection of excluded minors.

Standard examples include planar graphs with two excluded minors ($K_5$ and $K_{3,3}$) and knotlessly embeddable graphs with the Petersen family as excluded minors.

However in general, a finite list is not necessarily a short list, and there are natural properties with large numbers of excluded minors. In fact, I recall seeing examples where astronomical numbers of excluded minors have been proved to exist - unfortunately for the life of me, I can't remember these examples and I can't find them on MathSciNet.

So my question is: please give me references to results that show the existence of vast numbers of excluded minors for natural minor-closed classes of graphs.

Answer 1

Here is another answer that I just recently learned about that I find quite shocking. A graph is called $Y \Delta Y$ reducible if it can be reduced to isolated vertices by applying any of the following six operations.

1. Delete a loop.
2. Delete a degree one vertex.
3. Replace a pair of parallel edges by a single edge.
4. Replace an induced path by a single edge.
5. $Y \Delta$ transformation: Delete a degree 3 vertex $w$ and its three incident edges $wx, wy$ and $wz$, and add three edges $xy, yz$ and $xz$.
6. $\Delta Y$ transformation: Delete the three edges of a triangle $\Delta:=xyz$, and add a new vertex $w$ and three new edges $wx, wy$ and $wz.$

Truemper showed that the class of $Y \Delta Y$ reducible graphs is minor-closed. Epifanov proved that all planar graphs are $Y \Delta Y$ reducible. Recently, Yu showed that there are more than 68 billion excluded minors for $Y \Delta Y$ reducibility.

Specically, Yu finds 68897913659 graphs that are excluded minors (up to isomorphism).

Answer 2

Here is a follow-up to Richard Stanley's comment. In his Master's thesis Hunting for torus obstructions (University of Victoria, 2002), Chambers (together with his adviser Myrvold) studied the forbidden minors (and forbidden topological minors) for embeddability on the torus.

According to this paper:

To date, Myrvold and Chambers have found 239,322 topological obstructions and 16,629 minor order obstructions that include those on up to eleven vertices, the 3-regular ones on up to 24 vertices, the disconnected ones and those with a cut-vertex. Previously, only a few thousand had been determined.

I am guessing that this was done by computer search, but I couldn't access the thesis from the UVic library.