Disjoint dijoins

DOI10.1016/J.JCTB.2016.04.002MaRDI QIDQ290802zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Katherine Edwards, Ringi Kim, Alex Scott, Paul Seymour

Publication date 3 June 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.1415

zbMATH Keywords

disjoint dijoinsfeedback arc setLucchesi-Younger theoremWoodall's conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Abstract: 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, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S is a subset of the edges of G that 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.

Recommendations

• Disjoint dijoins for classes of dicuts in finite and infinite digraphs
• On dijoins
• Disjoint paths in acyclic digraphs
• A note on disjoint dijoins
• scientific article; zbMATH DE number 2246594

Cites work

• A counterexample to a conjecture of Edmonds and Giles
• A Minimax Theorem for Directed Graphs
• scientific article; zbMATH DE number 3606472 (Why is no real title available?)
• On dijoins

Cited in

(11)

• A note on disjoint dijoins
• Disjoint NP-Pairs
• Disjoint dijoins for classes of dicuts in finite and infinite digraphs
• scientific article; zbMATH DE number 2246594 (Why is no real title available?)
• On dijoins
• On the infinite Lucchesi–Younger conjecture I
• On Packing Dijoins in Digraphs and Weighted Digraphs
• Strong orientation of a connected graph for a crossing family
• Dyadic packing of dijoins
• Approximately packing Dijoins via nowhere-zero flows
• A min-max relation on dicuts and dijoins in weighted chordal digraphs

This page was built for publication: Disjoint dijoins

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290802)