Locally chordal graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914213238145024 |
|---|---|
| author | Abrishami, Tara Knappe, Paul Kobler, Jonas |
| author_facet | Abrishami, Tara Knappe, Paul Kobler, Jonas |
| contents | 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 of the classic descriptions of chordal graphs via induced subgraphs and via minimal separators. For the latter, we rely on the local separators introduced in [CJKK25]. Another characterization is via the local covering, which was introduced in [DJKK22] to study local-global characteristics of graphs using coverings from topology. Our final characterization of locally chordal graphs is in terms of their binary cycle spaces. This gives a new characterization of chordal graphs as wheel-free graphs whose binary cycle space is generated by triangles.
Together, these results demonstrate the potential of local-global tools to uncover rich new properties. Our results in this paper also form the basis of our local-global analysis of locally chordal graphs [AKb], where we develop a local-global perspective into structural characterizations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17320 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Locally chordal graphs Abrishami, Tara Knappe, Paul Kobler, Jonas Combinatorics 05C83, 05C69, 05C40, 05C38 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 of the classic descriptions of chordal graphs via induced subgraphs and via minimal separators. For the latter, we rely on the local separators introduced in [CJKK25]. Another characterization is via the local covering, which was introduced in [DJKK22] to study local-global characteristics of graphs using coverings from topology. Our final characterization of locally chordal graphs is in terms of their binary cycle spaces. This gives a new characterization of chordal graphs as wheel-free graphs whose binary cycle space is generated by triangles. Together, these results demonstrate the potential of local-global tools to uncover rich new properties. Our results in this paper also form the basis of our local-global analysis of locally chordal graphs [AKb], where we develop a local-global perspective into structural characterizations. |
| title | Locally chordal graphs |
| topic | Combinatorics 05C83, 05C69, 05C40, 05C38 |
| url | https://arxiv.org/abs/2501.17320 |