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

Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number6
JournalAdvances in Combinatorics
Volume2022
Issue number1
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth'. Together they form a unique fingerprint.

Cite this