Coarse Gallai conjecture for A-paths

Let GG be a graph and let AA be a subset of the vertices of GG. An AA-path is a path in GG whose two endpoints belong to AA. For subsets XX of vertices of GG and integers r0r\geq 0, let BG(X,r)B_G(X,r) denote the set of vertices at distance at most rr from XX. Two subgraphs are at distance at least dd if the distance between their vertex sets is at least dd. Coarse Gallai conjecture. There exist functions f:NNf:\mathbb N\to\mathbb N and g:NNg:\mathbb N\to\mathbb N such that for all positive integers kk and dd, for every graph GG and every subset AA of the vertices of GG, either GG contains kk AA-paths which are pairwise at distance at least dd, or there exists a set XX of the vertices of GG with Xf(k)|X|\leq f(k) such that every AA-path in GG contains a vertex of BG(X,g(d))B_G(X,g(d)). This strengthens the coarse Erdős–Pósa-type statement by requiring the radius of the hitting balls to depend only on dd, while the size of the hitting set depends only on kk.

Sources & referencesView supporting material

Primary source

Marc Distel, Ugo Giocanti, Jędrzej Hodor, Clément Legrand-Duchesne and Piotr Micek, “A coarse Gallai theorem”, arXiv:2601.18439 (2026).

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.