Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jctb.2016.04.002 | J. Comb. Theory, Ser. B |
DocType | Volume | Issue |
Journal | 120 | C |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Katherine Edwards | 2 | 24 | 5.50 |
| ringi kim | 3 | 7 | 2.96 |
| Alex Scott | 4 | 251 | 40.93 |
| Paul D. Seymour | 5 | 2786 | 314.49 |