Disjoint dijoins

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

Research output: Contribution to journalArticlepeer-review

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⊆ 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.

Original languageEnglish (US)
Pages (from-to)18-35
Number of pages18
JournalJournal of Combinatorial Theory. Series B
Volume120
DOIs
StatePublished - Sep 1 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Disjoint dijoins
  • Feedback arc set
  • Lucchesi-Younger theorem
  • Woodall's conjecture

Fingerprint Dive into the research topics of 'Disjoint dijoins'. Together they form a unique fingerprint.

Cite this