11 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…
The global structure of locally chordal graphs
Tara Abrishami, Paul Knappe
A graph is locally chordal if each of its small-radius balls is chordal. In an earlier work [AKK25], the authors and Kobler proved that locally chordal graphs can be characterized…
Locally interval graphs are circular-arc graphs
Tara Abrishami, Sandra Albrechtsen, Nathan Bowler +2
Circular-arc graphs are graphs that can be represented as intersection graphs of subpaths of a cycle. Interval graphs are graphs that can be represented as intersection graphs of s…
Locally chordal graphs
Tara Abrishami, Paul Knappe, Jonas Kobler
In this paper we study locally chordal graphs, i.e. graphs where every small-radius ball is chordal. We prove four characterizations of locally chordal graphs. Two are counterparts…