Displaying blocking pairs in signed graphs

ACO Seminar
Thursday, October 28, 2010 - 16:30
1.5 hours (actually 80 minutes)
Skiles 255
Dept. of Combinatorics and Optimization, University of Waterloo
A signed graph is a pair (G, \Sigma) where G is a graph and \Sigma is a subset of the edges of G. A cycle C in G is even (resp. odd) if E(C) \cap \Sigma is even (resp. odd). A blocking pair in a signed graph is a pair of vertices {x, y} such that every odd cycle in (G, \Sigma) intersects at least one of the vertices x and y. Blocking pairs arise in a natural way in the study of even cycle matroids on signed graphs as well as signed graphs with no odd K_5 minor. In this article, we characterize when the blocking pairs of a signed graph can be represented by 2-cuts in an auxiliary graph. We discuss the relevance of this result to the problem of characterizing signed graphs with no odd K_5 minor and determing when two signed graphs represent the same even cycle matroid. This is joint work with Irene Pivotto and Paul Wollan.