Geodesic
Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
Advances in Combinatorics (2022) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)-free graph $G$ has treewidth at most $c\log (|V(G)|)$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth. Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $G$ excluding the so-called three-path-configurations as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and Coloring admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph.
Publié le : 
@article{ADVC_2022_a3,
     author = {Tara Abrishami and Maria Chudnovsky and Sepehr Hajebi and Sophie Spirkl},
     title = {Induced subgraphs and tree decompositions {III.} {Three-path-configurations} and logarithmic treewidth},
     journal = {Advances in Combinatorics},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADVC_2022_a3/}
}
TY  - JOUR
AU  - Tara Abrishami
AU  - Maria Chudnovsky
AU  - Sepehr Hajebi
AU  - Sophie Spirkl
TI  - Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
JO  - Advances in Combinatorics
PY  - 2022
UR  - http://geodesic.mathdoc.fr/item/ADVC_2022_a3/
LA  - en
ID  - ADVC_2022_a3
ER  - 
%0 Journal Article
%A Tara Abrishami
%A Maria Chudnovsky
%A Sepehr Hajebi
%A Sophie Spirkl
%T Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
%J Advances in Combinatorics
%D 2022
%U http://geodesic.mathdoc.fr/item/ADVC_2022_a3/
%G en
%F ADVC_2022_a3
Tara Abrishami; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth. Advances in Combinatorics (2022). http://geodesic.mathdoc.fr/item/ADVC_2022_a3/