7
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Aug 9, 2017 at 2:56

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 at 18:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .