Abstract | ||
---|---|---|
Given a connected graph G=(V,E) and three even-sized subsets A"1, A"2, A"3 of V, when does V have a partition (S"1,S"2) such that G[S"i] is connected and |S"i@?A"j| 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 |A"1|=|A"2|=|A"3|=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. The purpose of this paper is to present a complete solution to this problem based on a strengthening of Seymour@?s theorem on triples in matroid circuits. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.jctb.2011.08.005 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
binary matroids,special case,general problem,parity constraint,integer flow theory,own right,connected graph,theoretical interest,even-sized subsets,matroid circuit,complete solution,planar graph,bond | Matroid,Discrete mathematics,Combinatorics,Monad (category theory),Function composition,Connectivity,Partition (number theory),Mathematics,Planar graph,Special case,Binary number | Journal |
Volume | Issue | ISSN |
102 | 3 | 0095-8956 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xujin Chen | 1 | 231 | 30.54 |
Guoli Ding | 2 | 444 | 51.58 |
Xingxing Yu | 3 | 577 | 68.19 |
Wenan Zang | 4 | 305 | 39.19 |