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$
$\endgroup$
3
-
$\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 ProtsakCommented Jan 4, 2016 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 HuynhCommented Jan 4, 2016 at 8:20
-
$\begingroup$ Exactly. @Tony, many thanks for your clarifications and answer. $\endgroup$– user31016Commented Jan 5, 2016 at 9:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jan 3, 2016 at 8:39