Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number

Abstract

We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by $Kω(G)^s |V(G)|^{1-β}$ for fixed $K,s,β>0$, and to admitting balanced clique-based separators of strongly sublinear size (equivalently, weight). Thus, we show that all these properties, which arose independently in the study of subexponential-time exact algorithms and polynomial-time approximation schemes, in fact describe the same hereditary graph classes. As a consequence of our equivalence theorem, we also show that every hereditary class $\mathcal C$ with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given $G\in\mathcal C$, computes a tree decomposition of $G$ with strongly sublinear independence number.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Combinatorics

• arXiv preprint · 23 September 2026

  Minimal representations of topology-preserving quantum-like states

  William Horvat, Debadrita Saha, Nicolás Gigena and 2 others
• arXiv preprint · 21 September 2026

  Dual-GNN Multilevel Coarsening for Maximum Independent Set

  Tianfeng Chen and Xianyue Li
• arXiv preprint · 23 September 2026

  Sampling Line-Graph Colorings with Constant Extra Colors

  Alireza Haqi
• arXiv preprint · 21 September 2026

  PermuFormer: Multi-Task Pretraining for Permutation Representation in Algebraic Combinatorics

  Henry Kvinge
• arXiv preprint · 23 September 2026

  A 27 x 27 x 27 counterexample to Comon's conjecture

  Benjamin Lovitz

All new papers in Combinatorics