Disjoint dijoins

详细信息    查看全文

• 作者：Maria Chudnovsky^a ; ¹ ; Katherine Edwards^b ; ² ; Ringi Kim^c ; Alex Scott^d ; Paul Seymour^c ; ³ ; ^{pds@math.princeton.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Lucchesi&ndash ; Younger theorem ; Disjoint dijoins ; Woodall's conjecture ; Feedback arc set
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：120
• 期：Complete
• 页码：18-35
• 全文大小：418 K

文摘

A “dijoin” in a digraph is a set of edges meeting every directed cut. D.R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths.

We conjecture that when k=2$k=2$, the disconnectedness of S is crucial: more precisely, that if G   is a digraph, and S⊆E(G)$S\subseteq E(G)$ forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins.

We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.