A graph $H$ is an odd minor of a graph $G$ if $H$ arises from $G$ by first deleting some vertices and edges and then contracting all edges in some edge cut.

Is it known that families of graphs that are characterized by a list of forbidden odd minors are characterized by a finite list of forbidden odd minors?

  • $\begingroup$ I am pretty sure that the well-quasi-ordering result of binary matroids would imply the well-quasi-ordering of graphs under odd minors. I also remember hearing Tony Huynh talking on structure of "group-labelled" graphs with a forbidden minors. Perhaps, though not everything is published, it must be known. $\endgroup$ – Sang-il Aug 9 '17 at 2:56

Yes, this is true, but the result is still being written up by Geelen, Gerards and Whittle as part of their Matroid Minors Project.

Also, for any fixed signed graph $H$, there is a polynomial-time algorithm to test if an input signed graph contains $H$ as a minor. Together with the positive answer to your question, this implies that there is a polynomial-time algorithm to test for any minor-closed property of signed graphs. See my PhD thesis for the algorithm (which works more generally for any $\Gamma$-labelled graph, where $\Gamma$ is a fixed finite abelian group).

In the thesis there is also a mention of the well-quasi-ordering result that you want (Theorem 1.1.9).

| cite | improve this answer | |
  • $\begingroup$ How do minors of signed graphs relate to odd minors? Is it obvious that the first includes the second as a special case? $\endgroup$ – Dan Cranston Aug 14 '17 at 17:18
  • $\begingroup$ If $H$ is an odd minor of $G$, then $(H, E(H))$ is a signed-minor of $(G, E(G))$. $\endgroup$ – Tony Huynh Aug 14 '17 at 18:08
  • $\begingroup$ But now that I think about it, this is not an if and only if since you do not allow re-signing and must contract all edges in an edge cut (and can only do this once). Thus, my answer does not answer your question; I'll think about it some more. $\endgroup$ – Tony Huynh Aug 14 '17 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.