Bonds with parity constraints

详细信息    查看全文

• 作者：Xujin Chen^a ; ¹ ; Guoli Ding^b ; ² ; ^{ding@math.lsu.edu} ; Xingxing Yu^c ; ³ ; Wenan Zang^d ; ⁴
• 关键词：Bond ; Parity condition ; 2-Linkage ; Planar graph
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2012
• 出版时间：May, 2012
• 年：2012
• 卷：102
• 期：3
• 页码：588-609
• 全文大小：421 K

文摘

Given a connected graph and three even-sized subsets , , of V, when does V have a partition such that is connected and is odd for all and ? This problem arises in the area of integer flow theory and has theoretical interest in its own right. The special case when 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.