Canonical tree-decompositions of chordal graphs

Abstract

We show that a locally finite, connected graph $G$ is $r$-locally chordal (that is, its $r/2$-balls are chordal) if and only if the unique canonical graph-decomposition ${\mathcal{H}}_r(G)$ of $G$ displaying its $r$-global structure is into cliques. Our proof relies on a canonical version of Halin's characterization of chordal locally finite graphs as those that admit a tree-decomposition into cliques: We show that such tree-decompositions can be chosen to be canonical, that is, so that they are invariant under all the graph's automorphisms.

arXiv commentv3: updated introduction; 20 pages, 1 figure; the results in this paper appeared in arXiv:2501.17320v1 which is now split into four separate papers