# Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision)

The Robertson-Seymour theorem says that the set of isomorphism classes of finite graphs, with the minor ordering ($G \le H$ if $G$ is a minor of $H$) is a well partial ordering (it is well-founded and has no infinite antichains).

Wikipedia currently says that if we replace the minor ordering by the "topological minor" ordering -- that is, $G\le H$ if some subdivision of $G$ can be embedded in $H$ -- then this is no longer a well partial order.

Unfortunately it gives no citation for this so I was hoping someone could either point me to a counterexample or come up with one. (Or tell me that in fact it's wrong, or that the problem is still open, etc.)

Obviously, this order is still well-founded, so a counterexample would have to take the form of an infinite antichain. (Well, or some other way of showing that something's not a wpo.)

I believe that an example of an infinite canonical antichain is constructed in this paper, in which it is proved that a minor closed class of graphs $\mathcal{G}$ is quasi-well-ordered by the topological minor relation if and only if some $B_n$ is not in $\mathcal{G}$, where $B_n$ is the path obtained from doubling each edge in an $(n+1)$-path.
• Ah, thanks! I'll upvote/accept/award this as soon as I get a chance to verify the antichain for myself. Note, by the way, that the antichain given in the paper is not $B_n$ (because in fact this is a chain -- each is a subgraph of the next), but rather what it calls $A_n$; $A_n$ is $B_{n-1}$, but with the two end vertices each having two self-loops in addition. (And I'm guessing by subdividing you could probably make an antichain of simple graphs too?) Feb 12, 2013 at 5:28
• @HarryAltman Would you mind elaborating on how to obtain an antichain by subdivision? If say you take the antichain $(A_n)_n$ where $A_n:=$ the edge-repeated n-path with loops on the two ends (as Fig 2 in Excluding a Long Double Path Minor), subdivide each $A_n$ into a simple graph $A'_n$, it is not obvious why $(A'_n)_n$ remains an antichain. Mar 7, 2022 at 6:09
• Thanks for your clarification, @HarryAltman. I still fail to see why $A_n\not\preceq A_m$ implies $A'_n\not\preceq A'_m$ for each $n<m$ though, where $A'_n$ is a subdivision of $A_n$ into simple graph. We seem to need $A_n\preceq A'_n$ and $A'_m\preceq A_m$ for the implication above to hold, but we only have $A_n\preceq A'_n$. Mar 11, 2022 at 0:15