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.

d="sp0050">We conjecture that when d="mmlsi1" class="mathmlsrc">data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300041&_mathId=si1.gif&_user=111111111&_pii=S0095895616300041&_rdoc=1&_issn=00958956&md5=3d70c76065ac7631bdbdf6765432d34f" title="Click to view the MathML source">k=2dden">de">$k=2$, the disconnectedness of S is crucial: more precisely, that if G   is a digraph, and d="mmlsi2" class="mathmlsrc">data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300041&_mathId=si2.gif&_user=111111111&_pii=S0095895616300041&_rdoc=1&_issn=00958956&md5=1f7caec36caafab5e36e99df6361a5a0" title="Click to view the MathML source">S⊆E(G)dden">de">$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.

d="sp0060">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.