5
$\begingroup$

This is a follow-up discussion on @296991, with further questions.

In the following discussion, "graphs" are finite but not necessarily simple (i.e. $|V(G)|<\infty,$ but allow loops and repeated edges). $H$ is a topological minor of $G$ ($H\preceq_{\textrm{topo.minor}}G$) if $H$ is a subdivision of a subgraph of $G$. A well quasi-order is a quasi-order without infinite antichain, i.e. $\nexists \{a_n\}_{n\in\omega}$ s.t. $\forall n<m$, $a_n\not\preceq a_m$.

It is known that the topological minor order is not a well quasi order on graphs, witnessed by e.g. the antichain $\underline{\{A_n\}_n}$ (from Excluding a long double path minor). Theorem 3.4 of the same paper proved that if $\mathscr{G}$ is a minor-closed class of graphs, then $(\mathscr{G},\preceq_{\textrm{topo.minor}})$ is a well-quasi-order iff $\mathscr{G}$ contains finitely many $A_n$'s. However the class of simple graphs is not minor-closed: contracting an edge in a triangle gives a non-simple path.

It was claimed in @Harry Altman's comment on @269961 that by subdivision, one may find a $\preceq_{\textrm{topo.minor}}$-antichain in the class of simple graphs as well. I wonder how this is achieved: in particular, if we subdivide e.g. each $A_n$ into a simple graph $A'_n$, it is not obvious to me that $A_n\not\preceq_{\textrm{topo.minor}} A_m\implies A'_n\not\preceq_{\textrm{topo.minor}} A'_m$.

Moreover, if subdivision does not work, are there any good sources proving or disproving the well-quasi-orderedness of (simple graphs, $\preceq_{\textrm{topo.minor}}$)?

Thank you.

$\endgroup$
1
  • $\begingroup$ Just gained enough "reputation" to comment. Will update the post once it's answered either there or here. $\endgroup$
    – Shaopeng
    Commented Mar 7, 2022 at 6:12

0

You must log in to answer this question.

Browse other questions tagged .