Woodall's conjecture: Bibliography

D. R. WoodallMenger and König systems.  In Y. Alavi and D.R. Lick, editors, Theory and Applications of Graphs, volume 642 of Lecture Notes in Mathematics, p.620–635. Springer, 1978.

D. R. WoodallMinimax theorems in graph theory.  In L. W. Beineke and R.J. Wilson, editors, Selected Topics in Graph Theory, pages 237–269. Academic Press, 1978.

C. L. Lucchesi and D. H. Younger.  A minimax theorem for directed graphsJ. of the London Math. Soc. (2), vol.17, pp.369–374, 1978.

Proves the dual of Woodall's conjecture: if every dijoin has k or more edges then there is a disjoint collection of at least k directed cuts.

J. Edmonds and R. Giles.  A min-max relation for submodular functions on graphs.  Volume 1 of Annals of Discrete Mathematics, pp.185–204. North-Holland, 1977.

States a generalized version of Woodall's conjecture (capacities on the arcs).

A. Schrijver.  A counterexample to a conjecture of Edmonds and GilesDiscrete Math., vol.32, pp.213–214, 1980.

Counterexample to the Edmonds-and-Giles generalization of Woodall's conjecture.

A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Number 24 in Algorithms and Combinatorics. Springer, 2003.

Chapter 56 (in volume B) gives an acocunt of Woodall's conjecure.

G. Cornuéjols and B. Guenin.  Note on dijoinsDiscrete Mathematics, vol.243, pp.213–216, 2002.

Gives two new counterexamples to the Edmonds-and-Giles generalization of Woodall's conjecture.

F. B. Shepherd and A. Vetta.  Visualizing, finding and packing dijoins.  In D. Avis, A. Hertz, and O. Marcotte, editors, Graph Theory and Combinatorial Optimization. Chapter 8, pp.219–254. Springer Verlag, 2005.

A. M. Williams.  Packing directed joins.  Master's thesis, University of Waterloo, 2004.

A. M. Williams and B. Guenin.  Advances in packing directed joins. Electronic Notes in Discrete Mathematics, vol.19, pp.249–255, 2005. [Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO2005)].

Special cases

J. Edmonds.  Edge-disjoint branchings.  In R. Rustin, editor, Combinatorial Algorithms, volume 9 of Courant Computer Science Symposium, pp.91–96. Algorithmics Press, 1973.

Shows (essentially) that Woodall's conjecture holds for dags having a single source or a single sink.

R. E. Tarjan,  A good algorithm for edge-disjoint branchings,  Information Processing Letters, vol.3, 1974, pp.51–53.

D.R. Fulkerson, G.C. Harding,  On edge-disjoint branchings, Networks vol.6, 1976, pp.97-104.

L. Lovász,  On two minimax theorems in graph theory, J. of Combinatorial Theory (B), vol.21, 1976, pp.96--103.

P. Feofiloff and D. H. Younger.  Directed cut transversal packing for source-sink connected graphsCombinatorica, vol.7, pp.255–263, 1987.

Proves Woddall's conjecture (with capacities on the arcs) for source-sink connected digraphs (every source connected to every sink by a directed path).

Y. Wakabayashi and O. Lee.  A note on a min-max conjecture of WoodallJ. Graph Theory. vol.38, pp.36–41, 2001.

Proves Woodall's conjecture for series-parallel digraphs.

Clutters

P. D. Seymour.  The matroids with max-flow min-cut propertyJ. of Combinatorial Theory (Ser. B), vol.23, pp.189–222, 1977.

G. Cornuéjols, B. Guenin, and F. Margot.  The packing propertyMathematical Programming (Ser. A), vol.89, pp.113–126, 2000.

G. Cornuéjols.  Combinatorial Optimization: Packing and Covering.  Volume 74 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM (Society for Industrial and Applied Mathematics), 2001.