Woodall's conjecture

From Egres Open
Jump to: navigation, search

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


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 [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


  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. 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
  9. O. Lee, A. Williams, Packing Dicycle Covers in Planar Graphs with No [math]K_5-e[/math] Minor, DOI link
  10. 10.0 10.1 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