7 citations · 14 across the 14 of their papers we have counts for
16 papers
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…
On vertex sets inducing tangles
Sandra Albrechtsen, Hanno von Bergen, Raphael W. Jacobs +2
Diestel, Hundertmark and Lemanczyk asked whether every -tangle in a graph is induced by a set of vertices by majority vote. We reduce their question to graphs whose size is boun…
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…
Linked tree-decompositions into finite parts
Sandra Albrechtsen, Raphael W. Jacobs, Paul Knappe +1
We prove that every graph which admits a tree-decomposition into finite parts has a rooted tree-decomposition into finite parts that is linked, tight and componental. As an applica…
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…
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…
Menger's Theorem in bidirected graphs
Nathan Bowler, Ebrahim Ghorbani, Florian Gut +2
Bidirected graphs are a generalisation of directed graphs that arises in the study of undirected graphs with perfect matchings. Menger's famous theorem - the minimum size of a set…
A Menger-type theorem for two induced paths
Sandra Albrechtsen, Tony Huynh, Raphael W. Jacobs +2
We give an approximate Menger-type theorem for when a graph contains two paths and such that is an induced subgraph of . More generally, we…
Efficiently distinguishing all tangles in locally finite graphs
Raphael W. Jacobs, Paul Knappe
While finite graphs have tree-decompositions that efficiently distinguish all their tangles, locally finite graphs with thick ends need not have such tree-decompositions. We show t…
A grid theorem for strong immersions of walls
Reinhard Diestel, Raphael W. Jacobs, Paul Knappe +1
We show that a graph contains a large wall as a strong immersion minor if and only if the graph does not admit a tree-cut decomposition of small 'width', which is measured in terms…
Canonical graph decompositions via coverings
Reinhard Diestel, Raphael W. Jacobs, Paul Knappe +1
We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degre…
The Lovász-Cherkassky theorem for locally finite graphs with ends
Raphael W. Jacobs, Attila Joó, Paul Knappe +2
Lovász and Cherkassky discovered independently that, if is a finite graph and such that the degree is even for every vertex , t…
Point sets and functions inducing tangles of set separations
Reinhard Diestel, Christian Elbracht, Raphael W. Jacobs
Tangles, as introduced by Robertson and Seymour, were designed as an indirect way of capturing clusters in graphs and matroids. They have since been shown to capture clusters in mu…
A Graph Theoretic Formula for the Number of Primes
R. Jacobs, C. E. Larson
Let PR be the graph whose vertices are with vertex adjacent to vertex if and only if . It is shown that , the the number of primes no…