On tree-decompositions for infinite chordal graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917361546690560 |
|---|---|
| author | Pitz, Max Real, Lucas Schaut, Roman |
| author_facet | Pitz, Max Real, Lucas Schaut, Roman |
| contents | A graph is chordal if it contains no induced cycle of length four or more. While finite chordal graphs are precisely those admitting tree-decompositions into cliques, this fails for infinite graphs. We establish two results extending the known theory to the infinite setting. Our first result strengthens sufficient conditions of Halin, Kříž-Thomas, and Chudnovsky-Nguyen-Scott-Seymour: We show that every chordal graph without a strict comb of cliques admits a tree-decomposition into maximal cliques. Our second result characterises the chordal graphs admitting tree-decompositions into finite cliques: a connected graph admits such a decomposition if and only if it is chordal, admits a normal spanning tree, and does not contain $\mathcal{H}$ $\unicode{x2013}$ an infinite clique with two non-adjacent dominating vertices $\unicode{x2013}$ as an induced minor. Combined with the characterisation of graphs with normal spanning trees, this yields a description by three types of forbidden minors. Both proofs proceed via greedy constructions of length $ω$, with the key new ingredient for the second result being an Extension Lemma that uses a finiteness theorem of Halin on minimal separators to produce suitable finite clique extensions at each step. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_24305 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On tree-decompositions for infinite chordal graphs Pitz, Max Real, Lucas Schaut, Roman Combinatorics 05C63, 05C40, 05C62, 05C69 A graph is chordal if it contains no induced cycle of length four or more. While finite chordal graphs are precisely those admitting tree-decompositions into cliques, this fails for infinite graphs. We establish two results extending the known theory to the infinite setting. Our first result strengthens sufficient conditions of Halin, Kříž-Thomas, and Chudnovsky-Nguyen-Scott-Seymour: We show that every chordal graph without a strict comb of cliques admits a tree-decomposition into maximal cliques. Our second result characterises the chordal graphs admitting tree-decompositions into finite cliques: a connected graph admits such a decomposition if and only if it is chordal, admits a normal spanning tree, and does not contain $\mathcal{H}$ $\unicode{x2013}$ an infinite clique with two non-adjacent dominating vertices $\unicode{x2013}$ as an induced minor. Combined with the characterisation of graphs with normal spanning trees, this yields a description by three types of forbidden minors. Both proofs proceed via greedy constructions of length $ω$, with the key new ingredient for the second result being an Extension Lemma that uses a finiteness theorem of Halin on minimal separators to produce suitable finite clique extensions at each step. |
| title | On tree-decompositions for infinite chordal graphs |
| topic | Combinatorics 05C63, 05C40, 05C62, 05C69 |
| url | https://arxiv.org/abs/2603.24305 |