Geelen's coarse Gallai conjecture for A-paths

Let GG be a finite or infinite graph and let AV(G)A\subseteq V(G). An AA-path is a path in GG between two distinct vertices of AA. Two subgraphs are at distance at least rr when the distance between their vertex sets is at least rr. A set is (a,b)(a,b)-centered if it is contained in the union of at most aa balls of radius at most bb. Geelen's coarse Gallai conjecture. There exist functions f,g:NRf,g:\mathbb N\rightarrow\mathbb R such that for any k,rNk,r\in\mathbb N, graph GG and AV(G)A\subseteq V(G), either there exist kk AA-paths pairwise at distance in GG at least rr, or there exists a set (f(k),g(r))(f(k),g(r))-centered in GG intersecting all AA-paths. The conjecture is a coarse version of Gallai's packing-covering theorem for AA-paths. The source does not state a resolution; its exact original formulation was reported as lost, and this is the formulation attributed to Geelen by Hendrey and Jacobs.

Sources & referencesView supporting material

Primary source

Chun-Hung Liu, “Coarse Menger property of quasi-minor excluded graphs and length spaces”, arXiv:2605.10068 (2026).

Additional references

2 papers in this index state this conjecture (2025–2026). The statement above is taken from the most recent of them; the others are arXiv:2512.17232.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.