Tree independence number I. (Even hole, diamond, pyramid)-free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, Kristina Vušković

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The tree-independence number (Formula presented.), first defined and studied by Dallard, Milanič, and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass (Formula presented.) of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that (Formula presented.) has bounded (Formula presented.). Via existing results, this yields a polynomial-time algorithm for the Maximum Weight Independent Set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milanič, and Štorgel that in a hereditary graph class, (Formula presented.) is bounded if and only if the treewidth is bounded by a function of the clique number.

Original languageEnglish (US)
Pages (from-to)923-943
Number of pages21
JournalJournal of Graph Theory
Volume106
Issue number4
DOIs
StatePublished - Aug 2024

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • algorithmic graph theory
  • even-hole-free graphs
  • structural graph theory
  • tree independence number
  • treewidth

Fingerprint

Dive into the research topics of 'Tree independence number I. (Even hole, diamond, pyramid)-free graphs'. Together they form a unique fingerprint.

Cite this