(Even hole, triangle)-free graphs revisited
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918425464406016 |
|---|---|
| author | Martins, Beatriz Trotignon, Nicolas |
| author_facet | Martins, Beatriz Trotignon, Nicolas |
| contents | We revisit a classical paper about (even hole, triangle)-free graphs [Conforti, Cornuéjols, Kapoor and Vu\v sković, Triangle-free graphs that are signable without even holes, Journal of Graph Theory, 34(3), 204--220, 2000]. In fact, the previous study describes a more general class, the so called triangle-free odd signable graphs, and we further generalise the class to the (theta, triangle, wac)-free graphs (not worth defining in an abstract).
We exhibit a stronger structure theorem, by precisely describing basic classes and separators. We prove that the separators preserve the treewidth and several properties. Some consequences are a recognition algorithm with running time $O(|V(G)|^4|E(G)|)$, a proof that the treewidth of graphs in the class is at most~4 (improving a previous bound of~5), and a simple criterion to decide if a graph in the class is planar. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_01816 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | (Even hole, triangle)-free graphs revisited Martins, Beatriz Trotignon, Nicolas Combinatorics Discrete Mathematics 05C75, 05C85 G.2.2 We revisit a classical paper about (even hole, triangle)-free graphs [Conforti, Cornuéjols, Kapoor and Vu\v sković, Triangle-free graphs that are signable without even holes, Journal of Graph Theory, 34(3), 204--220, 2000]. In fact, the previous study describes a more general class, the so called triangle-free odd signable graphs, and we further generalise the class to the (theta, triangle, wac)-free graphs (not worth defining in an abstract). We exhibit a stronger structure theorem, by precisely describing basic classes and separators. We prove that the separators preserve the treewidth and several properties. Some consequences are a recognition algorithm with running time $O(|V(G)|^4|E(G)|)$, a proof that the treewidth of graphs in the class is at most~4 (improving a previous bound of~5), and a simple criterion to decide if a graph in the class is planar. |
| title | (Even hole, triangle)-free graphs revisited |
| topic | Combinatorics Discrete Mathematics 05C75, 05C85 G.2.2 |
| url | https://arxiv.org/abs/2604.01816 |