Skip to main content
MathOverflow

Return to Question

deleted 4 characters in body
Source Link
user31016
user31016
  • 311
  • 1
  • 7

Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the productsum 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).

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

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

expanded on definition of minors for signed graphs and added some tags.
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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. A contractionWhen taking minors, any edge may only be performed on andeleted, but only even edgeedges 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).

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. A contraction may only be performed on an even edge (but an odd edge may be changed to even using any appropriate resigning and then a contraction may be performed along that edge).

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

Source Link
user31016
user31016
  • 311
  • 1
  • 7

Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?

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. A contraction may only be performed on an even edge (but an odd edge may be changed to even using any appropriate resigning and then a contraction may be performed along that edge).