Coarse Gallai conjecture for A-paths
Coarse Gallai conjecture for A-paths
Let be a graph and let be a subset of the vertices of . An -path is a path in whose two endpoints belong to . For subsets of vertices of and integers , let denote the set of vertices at distance at most from . Two subgraphs are at distance at least if the distance between their vertex sets is at least . Coarse Gallai conjecture. There exist functions and such that for all positive integers and , for every graph and every subset of the vertices of , either contains -paths which are pairwise at distance at least , or there exists a set of the vertices of with such that every -path in contains a vertex of . This strengthens the coarse Erdős–Pósa-type statement by requiring the radius of the hitting balls to depend only on , while the size of the hitting set depends only on .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.