8 papers · 1 filter
The coarse Erdős-Pósa theorem
Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf +1
We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. Informally, any graph either contains many fat cycles that are pairwise far apart, or there is a small nu…
A coarse block-cutvertex tree-decomposition
Sandra Albrechtsen, Agelos Georgakopoulos
We obtain a coarse version of the block-cutvertex tree-decomposition of a connected graph.
A coarse Menger theorem for hyperbolic graphs, finitely presented groups, and more
Sandra Albrechtsen
Menger's theorem is one of the most fundamental results in graph theory. It states that if a graph does not contain disjoint paths between two given sets and of ver…
Small counterexamples to the fat minor conjecture
Sandra Albrechtsen, Marc Distel, Agelos Georgakopoulos
We narrow the gap between the family of graphs that do and the family of graphs that do not satisfy the fat minor conjecture by obtaining much simpler counterexamples than were pre…
Excluding as a fat minor
Sandra Albrechtsen, Marc Distel, Agelos Georgakopoulos
We prove that for every , the graph satisfies the fat minor conjecture of Georgakopoulos and Papasoglu: for every there exist $M,A\in…
Counterexample to the conjectured coarse grid theorem
Sandra Albrechtsen, James Davies
We show that for every there exists a graph that does not contain the -grid as a -fat minor and is not -quasi-isometric to a g…
A coarse Halin Grid Theorem with applications to quasi-transitive, locally finite graphs
Sandra Albrechtsen, Matthias Hamann
We prove a coarse version of Halin's Grid Theorem: Every one-ended, locally finite graph that contains the disjoint union of infinitely many rays as an asymptotic minor also contai…
Asymptotic half-grid and full-grid minors
Sandra Albrechtsen, Matthias Hamann
We prove that every locally finite, quasi-transitive graph with a thick end whose cycle space is generated by cycles of bounded length contains the full-grid as an asymptotic minor…