Strongly chordal graphs as intersection graphs of trees (Farber's proof revisited)
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917953907195904 |
|---|---|
| author | Biedl, Therese |
| author_facet | Biedl, Therese |
| contents | In his Ph.D. thesis, Farber proved that every strongly chordal graph can be represented as intersection graph of subtrees of a weighted tree, and these subtrees are ``compatible''. Moreover, this is an equivalent characterization of strongly chordal graphs. To my knowledge, Farber never published his results in a conference or a journal, and the thesis is not available electronically. As a service to the community, I therefore reproduce the proof here.
I then answer some questions that naturally arise from the proof. In particular, the sufficiency proof works by showing the existence of a simple vertex. I give here an alternate sufficiency proof that directly converts a set of compatible subtrees into a strong elimination order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_09440 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strongly chordal graphs as intersection graphs of trees (Farber's proof revisited) Biedl, Therese Combinatorics Computational Geometry In his Ph.D. thesis, Farber proved that every strongly chordal graph can be represented as intersection graph of subtrees of a weighted tree, and these subtrees are ``compatible''. Moreover, this is an equivalent characterization of strongly chordal graphs. To my knowledge, Farber never published his results in a conference or a journal, and the thesis is not available electronically. As a service to the community, I therefore reproduce the proof here. I then answer some questions that naturally arise from the proof. In particular, the sufficiency proof works by showing the existence of a simple vertex. I give here an alternate sufficiency proof that directly converts a set of compatible subtrees into a strong elimination order. |
| title | Strongly chordal graphs as intersection graphs of trees (Farber's proof revisited) |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2503.09440 |