Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909562415611904 |
|---|---|
| author | Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| author_facet | Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| contents | A generalized $t$-pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar by identifying simplicial vertices. We prove that for every integer $t$ there exists a constant $c(t)$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ and no induced subgraph isomorphic to a generalized $t$-pyramid has treewidth at most $c(t)\log{n}$. This settles a special case of a conjecture of Sintiari and Trotignon; this bound is also best possible for the class. It follows that several \textsf{NP}-hard problems such as \textsc{Stable Set}, \textsc{Vertex Cover}, \textsc{Dominating Set} and \textsc{Coloring} admit polynomial-time algorithms on this class of graphs. Results from this paper are also used in later papers of the series, in particular to solve the full version of the Sintiari-Trotignon conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_13684 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Combinatorics A generalized $t$-pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar by identifying simplicial vertices. We prove that for every integer $t$ there exists a constant $c(t)$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ and no induced subgraph isomorphic to a generalized $t$-pyramid has treewidth at most $c(t)\log{n}$. This settles a special case of a conjecture of Sintiari and Trotignon; this bound is also best possible for the class. It follows that several \textsf{NP}-hard problems such as \textsc{Stable Set}, \textsc{Vertex Cover}, \textsc{Dominating Set} and \textsc{Coloring} admit polynomial-time algorithms on this class of graphs. Results from this paper are also used in later papers of the series, in particular to solve the full version of the Sintiari-Trotignon conjecture. |
| title | Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2307.13684 |