Journal article icon

Journal article

Disjoint dijoins

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

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jctb.2016.04.002

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Publisher:
Elsevier
Journal:
Journal of Combinatorial Theory. Series B More from this journal
Volume:
120
Pages:
18-35
Publication date:
2016-01-01
Acceptance date:
2016-04-02
DOI:
EISSN:
1096-0902
ISSN:
0095-8956
Keywords:
Pubs id:
pubs:618099
UUID:
uuid:a7a4ffe7-4531-4a4d-bd94-b33191a34fd0
Local pid:
pubs:618099
Source identifiers:
618099
Deposit date:
2016-07-09

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP