TY - JOUR

T1 - Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Hajebi, Sepehr

AU - Spirkl, Sophie

N1 - Funding Information:
*Supported by NSF Grant DMS-1763817 and NSF-EPSRC Grant DMS-2120644. †We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912].
Publisher Copyright:
© 2022 Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl.

PY - 2022

Y1 - 2022

N2 - 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 H of graphs, we say a graph G is H-free if no induced subgraph of G is isomorphic to a member of 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.

AB - 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 H of graphs, we say a graph G is H-free if no induced subgraph of G is isomorphic to a member of 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.

UR - http://www.scopus.com/inward/record.url?scp=85138599706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85138599706&partnerID=8YFLogxK

U2 - 10.19086/aic.2022.6

DO - 10.19086/aic.2022.6

M3 - Article

AN - SCOPUS:85138599706

VL - 2022

JO - Advances in Combinatorics

JF - Advances in Combinatorics

SN - 2517-5599

IS - 1

M1 - 6

ER -