Woodall's conjecture: Bibliography

A. Abdi, M. Dalirrooyfard, M. Neuwohner. Strong orientation of a connected graph for a crossing family. arXiv:2411.13202, 2024.

G. Cornuéjols, S. Liu, R. Ravi. Approximately packing dijoins via nowhere-zero flows. arXiv:2311.04337, 2023.

A. Abdi, G. Cornuéjols, M. Zlatin. On packing dijoins in digraphs and weighted digraphs. SIAM Journal on Discrete Mathematics, 37, 2417-2461, 2023.

J. P. Gollin, K. Heuer, K. Stavropoulos. Disjoint dijoins for classes of dicuts in finite and infinite digraphs. Combinatorial Theory, 2022.

M. Chudnovsky, K. Edwards, R. Kim, A. Scott, P. Seymour. Disjoint dijoins. Journal of Combinatorial Theory, Series B, v.120, 2016.

A. Schrijver. Observations on Woodall's Conjecture. 2013.

F. B. Shepherd, 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, 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)].

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

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

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

A. Schrijver. Min-max relations for directed graphs. Annals of Discrete Mathematics vol.16, pp.261–280, North-Holland, 1982.

A. Schrijver. A counterexample to a conjecture of Edmonds and Giles. Discrete Mathematics, vol.32, pp.213–214, 1980.

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

D. R. Woodall. Menger and König systems. Lecture Notes in Mathematics, vol.642, pp.620–635. Springer, 1978.

D. R. Woodall. Minimax theorems in graph theory. Selected Topics in Graph Theory, pp.237–269. Academic Press, 1978.

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

Special cases

G. Cornuéjols, S. Liu, R. Ravi. Packing dijoins in weighted chordal digraphs. arXiv:2501.10918, 2025.

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

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

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

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

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

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

WWW sites

Problem 12 in the collection of problems of the Egerváry Research Group on Combinatorial Optimization (EGRES)

Woodall's conjecture, Egerváry Research Group on Combinatorial Optimization (EGRES)

Woodall's Conjecture. In Open Problemas Garden, hosted by CSI of Charles University

Cuts in Digraphs and Woodall's Conjecture. In Problems in Topological Graph Theory, compiled by Dan Archdeacon

Clutters

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.

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

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