Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the product 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).
2 of 3
expanded on definition of minors for signed graphs and added some tags.
Tony Huynh
- 32.1k
- 11
- 112
- 187
Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?
user31016
- 311
- 1
- 7