8 papers
A structural duality for path-decompositions into parts of small radius
Sandra Albrechtsen, Reinhard Diestel, Ann-Kathrin Elm +4
It is an easy observation that if a graph~ admits a path-decomposition whose parts have small radius, then contains no large subdivision of or as a (quasi-)g…
Canonical tree-decompositions of chordal graphs
Raphael W. Jacobs, Paul Knappe
We show that a locally finite, connected graph is -locally chordal (that is, its -balls are chordal) if and only if the unique canonical graph-decomposition $\mathcal{H…
Canonical graph decompositions via local separations
Raphael W. Jacobs, Paul Knappe, Jan Kurkofka
Every finite graph can be decomposed in a canonical way that displays its local connectivity-structure [DJKK26]. These decompositions are defined via a suitable more tree-like…
Hitting cycles through prescribed vertices or edges
Nathan Bowler, Ebrahim Ghorbani, Florian Gut +2
We prove that for every set of vertices of a directed graph , the maximum number of vertices in contained in a collection of vertex-disjoint cycles in is at least th…
A characterisation of graphs quasi-isometric to -minor-free graphs
Sandra Albrechtsen, Raphael W. Jacobs, Paul Knappe +1
We prove that there is a function such that every graph with no -fat minor is -quasi-isometric to a graph with no minor. This solves the -case of a ge…
Counterexamples regarding linked and lean tree-decompositions of infinite graphs
Sandra Albrechtsen, Raphael W. Jacobs, Paul Knappe +1
Kriz and Thomas showed that every (finite or infinite) graph of tree-width admits a lean tree-decomposition of width . We discuss a number of counterexamples…