Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
Advances in Combinatorics · 2022
DOI: 10.19086/aic.2022.6 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Combinatorics, 2022. Verfasst von Maria Chudnovsky und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).
Abstract (Originalsprache)
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 $k$-Coloring (for fixed $k$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph.
Zitieren
APA
Chudnovsky, M., Abrishami, T., Hajebi, S., & Spirkl, S. (2022). Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth. Advances in Combinatorics. https://doi.org/10.19086/aic.2022.6
Vancouver
Chudnovsky M, Abrishami T, Hajebi S, Spirkl S. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth. Advances in Combinatorics. 2022. doi:10.19086/aic.2022.6
BibTeX
@article{Chudnovsky2022,
author = {Chudnovsky, Maria and Abrishami, Tara and Hajebi, Sepehr and Spirkl, Sophie},
title = {Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth},
journal = {Advances in Combinatorics},
year = {2022},
doi = {10.19086/aic.2022.6}
}
EUVIMED