Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.16258 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913776886874112 |
|---|---|
| author | Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Vušković, Kristina |
| author_facet | Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Vušković, Kristina |
| contents | The tree-independence number tree-$α$, first defined and studied by Dallard, Milanič and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem.
Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass $\mathcal C$ of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that $\mathcal C$ has bounded tree-$α$. Via existing results, this yields a polynomial time algorithm for the maximum independent set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milanič and Štorgel that in a hereditary graph class, tree-$α$ is bounded if and only if the treewidth is bounded by a function of the clique number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_16258 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tree independence number I. (Even hole, diamond, pyramid)-free graphs Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Vušković, Kristina Combinatorics The tree-independence number tree-$α$, first defined and studied by Dallard, Milanič and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass $\mathcal C$ of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that $\mathcal C$ has bounded tree-$α$. Via existing results, this yields a polynomial time algorithm for the maximum independent set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milanič and Štorgel that in a hereditary graph class, tree-$α$ is bounded if and only if the treewidth is bounded by a function of the clique number. |
| title | Tree independence number I. (Even hole, diamond, pyramid)-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2305.16258 |