# 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 [1] 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 [2] and independently Feofiloff and Younger [3] proved the conjecture for digraphs in which every sink-node is reachable from every source-node.
• Lee and Wakabayashi [4] showed that the conjecture is true for series-parallel digraphs.
• Mészáros [5] 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 [6] 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 [7][8]. Since the counterexample is planar, the more general conjecture is not true for planar graphs. Lee and Williams [9] showed however that it is true if the dual planar graph does not contain a $K_5-e$ 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 [10] proposed the following conjecture: If $k \geq 2$, then every 2k-dijoin in a digraph can be partitioned into 2 disjoint k-dijoins. He proved the following partial result:

Theorem[10]. If D=(V,A) is a directed graph and $F \subseteq A$ is a 2k-dijoin for $k \geq 2$, 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 [8] 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. [11] 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.

## References

1. D.R. Woodall, Menger and König systems, Theory and applications of graphs (Proc. Intern. Conf., Western Mich. Univ.), Lecture Notes in Math., 642 (1978) 620-635. DOI link
2. A. Schrijver, Min-max relations for directed graphs, Annals of Discrete Math. 16 (1982), 261-280, DOI link, author link
3. P. Feofiloff, D.H. Younger, Directed cut transversal packing for source-sink connected graphs, Combinatorica 7 (1987), 255-263. DOI link
4. O. Lee, Y. Wakabayashi, Note on a min-max conjecture of Woodall, J. Graph Theory 38 (2001), 36-41. DOI link
5. A. Mészáros, A note on disjoint dijoins, EGRES Quick Proof no. 2015-05
6. A. Schrijver, A counterexample to a conjecture of Edmonds and Giles, Discrete Math 32 (1980), 213-214, DOI link, ResearchGate link
7. G. Cornuéjols, B. Guenin, On dijoins, Discrete Mathematics 243 (2002), 213-216. DOI link
8. B. Guenin, A. M. Williams, Advances in packing directed joins, Electronic Notes in Discrete Mathematics 19 (2005), 249-255. DOI link
9. O. Lee, A. Williams, Packing Dicycle Covers in Planar Graphs with No $K_5-e$ Minor, DOI link
10. T. Király, A result on crossing families of odd sets, EGRES Technical Report no. 2007-10
11. M. Chudnovsky, K. Edwards, R. Kim, A. Scott, P. Seymour, Disjoint dijoins, Journal of Combinatorial Theory, Series B (2016), DOI link, author link