WorksMathematics
Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
Abstract
A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We show that 3PC-free graphs have logarithmic tree-independence number, which is asymptotically best possible.
Introduction
All graphs in this paper are finite and simple and all logarithms are base 2. We treat a graph and its vertex set interchangeably. Throughout this paper we use to denote the number of vertices of a graph . For graphs and , we say that is -free if no induced subgraph of is isomorphic to . For , we say that and are anticomplete if and there is no edge in with an end in and an end in . The closed neighborhood of a set , denoted by , is the set of vertices of that are in or have at least one neighbor in . For standard graph-theoretic terminology, the reader is referred to [4].
For a graph , a tree decomposition of consists of a tree and a map with the following properties:
(i) For every , there exists such that .
(ii) For every , there exists such that .
(iii) For every , the subgraph of induced by is connected.
The width of a tree decomposition is . The independence number of a tree decomposition is . The treewidth of , denoted by , is the minimum width of a tree decomposition of . The tree-independence number of , denoted by , is the minimum independence number of a tree decomposition of $G.
A path in a graph is an induced subgraph that is a path. The interior of a path is denoted by . A theta is a graph consisting of two non-adjacent vertices and three paths from to , such that is anticomplete to for . A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration.
It is known that 3PC-free graphs have polylogarithmic tree-independence number and if their clique number is bounded by a constant , then they also have logarithmic treewidth.
Theorem 1.1 (Abrishami, Chudnovsky, Hajebi, Spirkl [1]). For every there exists a constant such that if a graph is 3PC-free and -free, then .
Theorem 1.2 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [3]). There exists a constant such that if a graph with is 3PC-free, then .
On the other hand, the best lower bound on the tree-independence number of 3PC-free graphs is (Sintiari and Trotignon [7]). This led to a question [2, 3] of whether 3PC-free graphs with superlogarithmic tree-independence number exist.
Recently, Hajebi and Spirkl [5] introduced a powerful new notion of loose separability. A direct application of their method allows us to close the gap between the upper and the lower bounds. We prove:
Theorem 1.3. There exist constants such that if a graph with is 3PC-free, then .
Note that since the class of theta-free graphs is “-bounded” (see [6] for details), Theorem 1.3 yields another proof of Theorem 1.1.
Proof
We include some definitions from [3] and [5] that will be useful for us. If is a set of sets, a hitting set for is a set such that for every . For , a -system in is a set of non-empty subsets of , each of cardinality at most (thus, is allowed, whereas is not). We say that a -system in is anticomplete if every two distinct sets are anticomplete in . We denote the set of all -paths in by .
For , a graph is -loosely --separable if for every -system in , either
there is a hitting set for with ; or
there exist such that has a hitting set with ; in particular, and are anticomplete in .
For a graph , a function is a normal weight function on if . Let and let be a normal weight function on . A set is a -balanced separator if for every component of . The set is a -balanced separator if is a -balanced separator. For , a graph is -separator-dominated if for every normal weight function on , there exists with such that is a -balanced separator in .
Hajebi and Spirkl [5] prove:
Lemma 2.1 (Hajebi, Spirkl [5]). For all , there is a constant such that for every -free graph and every -system in , either there is a hitting set for with , or there is an anticomplete -system in with .
Lemma 2.2 (Hajebi, Spirkl [5]). Let and let be a -loosely --separable graph such that every induced subgraph of is -separator-dominated. Then, -.
The following was proved in [3]:
Theorem 2.3 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [3]). There is an integer with the following property. Let be a -free graph, and let be a normal weight function on . Then, there exists such that
, and
is a -balanced separator in $G.
Theorem 2.4 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [3]). Let be a -free graph and let be non-adjacent. Then, there is a hitting set for with .
Proof of Theorem 1.3: By Theorem 2.3, there exists an integer such that every -free graph is -separator-dominated. In particular, every induced subgraph of is -separator-dominated. Let be a -system in . Since is theta-free, is -free. By Lemma 2.1, there exists an integer such that either there is a hitting set for with , or there are two anticomplete sets . Let , , and let . Theorem 2.4 implies that there exists a hitting set for in with . Thus, has a hitting set with ; consequently, is -loosely --separable. By Lemma 2.2, -. This completes the proof.
AI Disclosure
We used GPT-6 Astra to proofread the manuscript. No AI tools were used to create the proof.
References
References
- [1]Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, and Sophie Spirkl. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth. Adv. Comb., pages Paper No. 6, 29, 2022.
- [2]Maria Chudnovsky and Sepehr Hajebi. Barbados Graph Theory Workshop, 2024.
- [3]Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov, and Sophie Spirkl. Tree independence number II. Three-path-configurations. Journal of Combinatorial Theory, Series B, 176:74–96, 2026.
- [4]Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Fifth edition, 2017.
- [5]Sepehr Hajebi and Sophie Spirkl. Tree-alpha and excluding finitely many graphs. 2026. arXiv:2605.01223.arxiv.org/abs/2605.01223
- [6]Alex Scott and Paul Seymour. A survey of χ-boundedness. Journal of Graph Theory, 95(3):473–504, 2020.
- [7]Ni Luh Dewi Sintiari and Nicolas Trotignon. (Theta, triangle)-free and (even hole, K₄)-free graphs—Part 1: Layered wheels. Journal of Graph Theory, 97(4):475–509, 2021.DOI