Woodall's conjecture

Is it true that if every directed cut in a digraph has at least k edges, then there are k disjoint dijoins?

Remarks

This question of Woodall is analogous to the Lucchesi-Younger theorem, by interchanging the terms cut and dijoin. It is easily seen to be true for k=2 (using the fact that the underlying undirected graph is 2-edge-connected), but open even for planar graphs in case of larger k. The following are some partial results:

• Schrijver and independently Feofiloff and Younger proved the conjecture for digraphs in which every sink-node is reachable from every source-node.
• Lee and Wakabayashi showed that the conjecture is true for series-parallel digraphs.
• Mészáros proved, using Olson's theorem, that if k is a prime power, then the conjecture holds if the underlying undirected graph is (k-1,1)-partition-connected. (It is easy to see that k-partition-connectivity is sufficient, since in that case the digraph can be decomposed into k weakly connected sub-digraphs.)

The counterexample of Schrijver

Originally a more general conjecture was proposed by Edmonds, Giles and Younger: every k-dijoin of a digraph can be partitioned into k dijoins. However, this was shown to be false by Schrijver even for k=2. His example is shown on the figure: the red edges form a 2-dijoin that cannot be partitioned into 2 dijoins.

Later other counterexamples have been found by Cornuéjols, Guenin and Williams . Since the counterexample is planar, the more general conjecture is not true for planar graphs. Lee and Williams showed however that it is true if the dual planar graph does not contain a [math]K_5-e[/math] minor. It is open if there is a function f(k) such that every f(k)-dijoin of a digraph can be partitioned into k dijoins.

Related conjectures

The following question is also open: is there an integer k such that if every directed cut has size at least k in a digraph, then it contains 3 disjoint dijoins?

Another weaker form is the following: is it true that if every directed cut in a digraph has size at least 2k, then there are 2 disjoint k-dijoins? As mentioned above, this is known to be true for k=1, but not known for larger values of k.

Király proposed the following conjecture: If [math]k \geq 2[/math], then every 2k-dijoin in a digraph can be partitioned into 2 disjoint k-dijoins. He proved the following partial result:

Theorem. If D=(V,A) is a directed graph and [math]F \subseteq A[/math] is a 2k-dijoin for [math]k \geq 2[/math], then F can be partitioned into two parts such that both contain at least k edges from every directed cut that contains at most 2k+1 edges from F.

Guenin and Williams conjecture the following: If a digraph D contains both a super-source (a source node from which all sinks are reachable) and a super-sink (a sink which is reachable from all sources), then all k-dijoins of D can be partitioned into k dijoins. This would be a generalization of the result on source-sink connected graphs. There is a counterexample where D contains a super-source but no super-sink.

In all known counterexamples to the conjecture of Edmonds, Giles, and Younger, the k-dijoin is not even weakly connected. Chudnovsky et al. conjecture that a weakly connected 2-dijoin of a digraph can always be partitioned into 2 dijoins. They prove this in two cases:

• if the 2-dijoin is a caterpillar subdivision (the underlying undirected graph is a tree where all nodes of degree at least three are on the same path),
• if the digraph itself is planar.

See also

• Woodall's conjecture in the Open Problem Garden
• A survey by Paulo Feofiloff
• Head-disjoint strongly connected orientations