Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges. For a given signed graph, a resigning may be performed by flipping the signs of all edges in the cutset of some vertex subset. Clearly this does not change the sign of any cycle. All possible resignings form an equivalence class. When taking minors, any edge may be deleted, but only even edges may be contracted (but an odd edge may be changed to even using any appropriate resigning and then a contraction may be performed along that edge).

  • $\begingroup$ "Clearly this does not change sign of any cycle" --- what about the sign of a 3-cycle $ABC$ after flipping the signs of the edges in the cutset of the set $\{A,B,C\}$? If you flip the signs of all 3 edges in this cycle, the sign would change. $\endgroup$ – Victor Protsak Jan 4 '16 at 8:03
  • $\begingroup$ @Victor Protsak: by cutset, user31016 means to take a subset $X$ of the vertices and to take all edges with exactly one endpoint in $X$ (this set of edges is usually called $\delta(X)$). $\endgroup$ – Tony Huynh Jan 4 '16 at 8:20
  • $\begingroup$ Exactly. @Tony, many thanks for your clarifications and answer. $\endgroup$ – user31016 Jan 5 '16 at 9:42

Yes. This is one of the results of the Matroid Minors Project of Geelen, Gerards and Whittle as part of their proof of Rota's Conjecture. In fact, they prove that for any finite abelian group $\Gamma$, the class of $\Gamma$-labelled graphs is well-quasi-ordered. Signed graphs correspond to the special case of $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$. I believe this result is still being written up though. However, the generalization of the Graph Minors Structure Theorem (which is a key ingredient of the proof of the Graph Minors Theorem) to group-labelled graphs has already appeared. See this paper of Geelen and Gerards.

| cite | improve this answer | |

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.