# 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.)

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 [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 ^{[10]} 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 ^{[10]}.** 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 ^{[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.

## See also

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

## References

- ↑ 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 - ↑ A. Schrijver,
*Min-max relations for directed graphs*, Annals of Discrete Math. 16 (1982), 261-280, DOI link, author link - ↑ P. Feofiloff, D.H. Younger,
*Directed cut transversal packing for source-sink connected graphs*, Combinatorica 7 (1987), 255-263. DOI link - ↑ O. Lee, Y. Wakabayashi,
*Note on a min-max conjecture of Woodall*, J. Graph Theory 38 (2001), 36-41. DOI link - ↑ A. Mészáros,
*A note on disjoint dijoins*, EGRES Quick Proof no. 2015-05 - ↑ A. Schrijver,
*A counterexample to a conjecture of Edmonds and Giles*, Discrete Math 32 (1980), 213-214, DOI link, ResearchGate link - ↑ G. Cornuéjols, B. Guenin,
*On dijoins*, Discrete Mathematics 243 (2002), 213-216. DOI link - ↑
^{8.0}^{8.1}B. Guenin, A. M. Williams,*Advances in packing directed joins*, Electronic Notes in Discrete Mathematics 19 (2005), 249-255. DOI link - ↑ O. Lee, A. Williams,
*Packing Dicycle Covers in Planar Graphs with No [math]K_5-e[/math] Minor*, DOI link - ↑
^{10.0}^{10.1}T. Király,*A result on crossing families of odd sets*, EGRES Technical Report no. 2007-10 - ↑ M. Chudnovsky, K. Edwards, R. Kim, A. Scott, P. Seymour,
*Disjoint dijoins*, Journal of Combinatorial Theory, Series B (2016), DOI link, author link