论文部分内容阅读
Given a connected graph G =(V, E) and three even-sized subsets A1, A2, A3 of V, when does V have a partition (S1, S2) such that G[Si] is connected and |Si∩Aj | is odd for all i =1, 2 and j =1, 2, 3? This problem arises in the area of integer flow theory and has theoretical interest in its own right.The special case when |A1| =|A2| =|A3| =2 has been resolved by Chakravarti and Robertson, and the general problem can be rephrased as a problem on binary matroids that asks if a given triple of elements is contained in a circuit.We present a complete solution to this problem based on a strengthening of Seymours theorem on triples in matroid circuits.