Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909112964481024 |
|---|---|
| author | Dallard, Clément Krnc, Matjaž Kwon, O-joung Milanič, Martin Munaro, Andrea Štorgel, Kenny Wiederrecht, Sebastian |
| author_facet | Dallard, Clément Krnc, Matjaž Kwon, O-joung Milanič, Martin Munaro, Andrea Štorgel, Kenny Wiederrecht, Sebastian |
| contents | Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs. Their result also implies a characterization of graph classes defined by finitely many forbidden induced subgraphs that are $(tw,ω)$-bounded, that is, treewidth can only be large due to the presence of a large clique. This condition is known to be satisfied for any graph class with bounded tree-independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. conjectured that $(tw,ω)$-boundedness is actually equivalent to bounded tree-independence number. We address this conjecture in the context of graph classes defined by finitely many forbidden induced subgraphs and prove it for the case of graph classes excluding an induced star. We also prove it for subclasses of the class of line graphs, determine the exact values of the tree-independence numbers of line graphs of complete graphs and line graphs of complete bipartite graphs, and characterize the tree-independence number of $P_4$-free graphs, which implies a linear-time algorithm for its computation. Applying the algorithmic framework provided in a previous paper of the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11222 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star Dallard, Clément Krnc, Matjaž Kwon, O-joung Milanič, Martin Munaro, Andrea Štorgel, Kenny Wiederrecht, Sebastian Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75 (Primary), 05C69, 05C76, 05C85 (Secondary) Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs. Their result also implies a characterization of graph classes defined by finitely many forbidden induced subgraphs that are $(tw,ω)$-bounded, that is, treewidth can only be large due to the presence of a large clique. This condition is known to be satisfied for any graph class with bounded tree-independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. conjectured that $(tw,ω)$-boundedness is actually equivalent to bounded tree-independence number. We address this conjecture in the context of graph classes defined by finitely many forbidden induced subgraphs and prove it for the case of graph classes excluding an induced star. We also prove it for subclasses of the class of line graphs, determine the exact values of the tree-independence numbers of line graphs of complete graphs and line graphs of complete bipartite graphs, and characterize the tree-independence number of $P_4$-free graphs, which implies a linear-time algorithm for its computation. Applying the algorithmic framework provided in a previous paper of the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes. |
| title | Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75 (Primary), 05C69, 05C76, 05C85 (Secondary) |
| url | https://arxiv.org/abs/2402.11222 |