betaFeedback

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 nn to denote the number of vertices of a graph GG. For graphs GG and HH, we say that GG is HH-free if no induced subgraph of GG is isomorphic to HH. For X,Y⊆V(G)X, Y \subseteq V(G), we say that XX and YY are anticomplete if X∩Y=∅X \cap Y = \varnothing and there is no edge in GG with an end in XX and an end in YY. The closed neighborhood of a set XX, denoted by N[X]N[X], is the set of vertices of GG that are in XX or have at least one neighbor in XX. For standard graph-theoretic terminology, the reader is referred to [4].

For a graph GG, a tree decomposition (T,χ)(T,\chi) of GG consists of a tree TT and a map χ:V(T)→2V(G)\chi: V(T) \to2^{V(G)} with the following properties:

(i) For every v∈V(G)v \in V(G), there exists t∈V(T)t \in V(T) such that v∈χ(t)v \in\chi(t).

(ii) For every uv∈E(G)uv \in E(G), there exists t∈V(T)t \in V(T) such that u,v∈χ(t)u,v \in\chi(t).

(iii) For every v∈V(G)v \in V(G), the subgraph of TT induced by {t∈V(T)∣v∈χ(t)}\{t \in V(T) \mid v \in\chi(t)\} is connected.

The width of a tree decomposition (T,χ)(T,\chi) is max⁡t∈V(T)∣χ(t)∣−1\max_{t \in V(T)} |\chi(t)| - 1. The independence number of a tree decomposition (T,χ)(T,\chi) is max⁡t∈V(T)α(χ(t))\max_{t \in V(T)} \alpha(\chi(t)). The treewidth of GG, denoted by tw⁡(G)\operatorname{tw}(G), is the minimum width of a tree decomposition of GG. The tree-independence number of GG, denoted by tree⁡-α(G)\operatorname{tree}\text{-}\alpha(G), 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 PP is denoted by P∗P^*. A theta is a graph consisting of two non-adjacent vertices a,ba, b and three paths P1,P2,P3P_1, P_2, P_3 from aa to bb, such that Pi∗P_i^* is anticomplete to Pj∗P_j^* for i≠ji \ne j. 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 tt, then they also have logarithmic treewidth.

Theorem 1.1 (Abrishami, Chudnovsky, Hajebi, Spirkl [1]). For every t∈Nt \in\mathbb{N} there exists a constant ctc_t such that if a graph GG is 3PC-free and KtK_t-free, then tw⁡(G)≤ctlog⁡n\operatorname{tw}(G) \le c_t \log n.

Theorem 1.2 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [3]). There exists a constant cc such that if a graph GG with n>1n > 1 is 3PC-free, then tree-α⁡(G)≤c(log⁡n)2\operatorname{tree-\alpha}(G) \le c(\log n)^2.

On the other hand, the best lower bound on the tree-independence number of 3PC-free graphs is log⁡n\log n (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 c,dc, d such that if a graph GG with n>1n > 1 is 3PC-free, then tree-α⁡(G)≤c+dlog⁡n\operatorname{tree-\alpha}(G) \le c + d \log n.

Note that since the class of theta-free graphs is “χ\chi-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 S\mathcal{S} is a set of sets, a hitting set for S\mathcal{S} is a set XX such that X∩Y≠∅X \cap Y \ne\varnothing for every Y∈SY \in\mathcal{S}. For b∈Nb \in\mathbb{N}, a bb-system S\mathcal{S} in GG is a set of non-empty subsets of V(G)V(G), each of cardinality at most bb (thus, S=∅\mathcal{S} = \varnothing is allowed, whereas S={∅}\mathcal{S} = \{\varnothing\} is not). We say that a bb-system S\mathcal{S} in GG is anticomplete if every two distinct sets S1,S2∈SS_1, S_2 \in\mathcal{S} are anticomplete in GG. We denote the set of all (X,Y)(X,Y)-paths in GG by PG(X,Y)\mathcal{P}_G(X,Y).

For b,c,d∈Nb, c, d \in\mathbb{N}, a graph GG is (b,c)(b,c)-loosely dd-α\alpha-separable if for every bb-system S\mathcal{S} in GG, either

  • there is a hitting set X⊆V(G)X \subseteq V(G) for S\mathcal{S} with α(X)≤c\alpha(X) \le c; or

  • there exist S1,S2∈SS_1, S_2 \in\mathcal{S} such that PG(S1,S2)\mathcal{P}_G(S_1,S_2) has a hitting set Y⊆V(G)∖(S1∪S2)Y \subseteq V(G) \setminus(S_1 \cup S_2) with α(Y)≤d\alpha(Y) \le d; in particular, S1S_1 and S2S_2 are anticomplete in GG.

For a graph GG, a function w:V(G)→[0,1]w : V(G) \to[0,1] is a normal weight function on GG if w(V(G))=1w(V(G)) = 1. Let c∈[0,1]c \in[0,1] and let ww be a normal weight function on GG. A set X⊆V(G)X \subseteq V(G) is a (w,c)(w,c)-balanced separator if w(D)≤cw(D) \le c for every component DD of G∖XG \setminus X. The set XX is a ww-balanced separator if XX is a (w,12)(w,\frac{1}{2})-balanced separator. For b∈Nb \in\mathbb{N}, a graph GG is bb-separator-dominated if for every normal weight function ww on GG, there exists X⊆V(G)X \subseteq V(G) with ∣X∣≤b|X| \le b such that N[X]N[X] is a ww-balanced separator in GG.

Hajebi and Spirkl [5] prove:

Lemma 2.1 (Hajebi, Spirkl [5]). For all a,b,q∈Na,b,q \in\mathbb{N}, there is a constant c2.1=c2.1(a,b,q)∈Nc_{2.1}=c_{2.1}(a,b,q) \in\mathbb{N} such that for every Ka,aK_{a,a}-free graph GG and every bb-system S\mathcal{S} in GG, either there is a hitting set X⊆V(G)X \subseteq V(G) for S\mathcal{S} with α(X)<c2.1\alpha(X)<c_{2.1}, or there is an anticomplete bb-system Q⊆S\mathcal{Q}\subseteq\mathcal{S} in GG with ∣Q∣≥q|\mathcal{Q}|\ge q.

Lemma 2.2 (Hajebi, Spirkl [5]). Let b,c,d∈Nb,c,d\in\mathbb{N} and let GG be a (b,c)(b,c)-loosely dd-α\alpha-separable graph such that every induced subgraph of GG is bb-separator-dominated. Then, tree⁡\operatorname{tree}-α(G)≤10c+5d\alpha(G)\le10c+5d.

The following was proved in [3]:

Theorem 2.3 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [3]). There is an integer bb with the following property. Let GG be a 3PC3PC-free graph, and let ww be a normal weight function on GG. Then, there exists Y⊆V(G)Y\subseteq V(G) such that

  • ∣Y∣≤b|Y|\le b, and

  • N[Y]N[Y] is a ww-balanced separator in $G.

Theorem 2.4 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [3]). Let GG be a 3PC3PC-free graph and let a,b∈V(G)a,b\in V(G) be non-adjacent. Then, there is a hitting set X⊆V(G)∖{a,b}X\subseteq V(G)\setminus\{a,b\} for PG({a},{b})P_G(\{a\},\{b\}) with α(X)≤32log⁡n\alpha(X)\le32\log n.

Proof of Theorem 1.3: By Theorem 2.3, there exists an integer bb such that every 3PC3PC-free graph is bb-separator-dominated. In particular, every induced subgraph of GG is bb-separator-dominated. Let S\mathcal{S} be a bb-system in GG. Since GG is theta-free, GG is K3,3K_{3,3}-free. By Lemma 2.1, there exists an integer cc such that either there is a hitting set X⊆V(G)X\subseteq V(G) for S\mathcal{S} with α(G[X])<c\alpha(G[X])<c, or there are two anticomplete sets S1,S2∈SS_1,S_2\in\mathcal{S}. Let s1∈S1s_1\in S_1, s2∈S2s_2\in S_2, and let Gs1s2=(G∖(S1∪S2))∪{s1,s2}G_{s_1s_2}=(G\setminus(S_1\cup S_2))\cup\{s_1,s_2\}. Theorem 2.4 implies that there exists a hitting set Ys1s2Y_{s_1s_2} for PGs1s2({s1},{s2})P_{G_{s_1s_2}}(\{s_1\},\{s_2\}) in Gs1s2G_{s_1s_2} with α(Ys1s2)≤32log⁡n\alpha(Y_{s_1s_2})\le32\log n. Thus, PG(S1,S2)P_G(S_1,S_2) has a hitting set Y=⋃s1∈S1,s2∈S2Ys1s2⊆V(G)∖(S1∪S2)Y=\bigcup_{s_1\in S_1,s_2\in S_2}Y_{s_1s_2}\subseteq V(G)\setminus(S_1\cup S_2) with α(G[Y])≤32b2log⁡n\alpha(G[Y])\le32b^2\log n; consequently, GG is (b,c)(b,c)-loosely (32b2log⁡n)(32b^2\log n)-α\alpha-separable. By Lemma 2.2, tree⁡\operatorname{tree}-α(G)≤10c+160b2log⁡n\alpha(G)\le10c+160b^2\log n. 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. [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. [2]Maria Chudnovsky and Sepehr Hajebi. Barbados Graph Theory Workshop, 2024.
  3. [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. [4]Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Fifth edition, 2017.
  5. [5]Sepehr Hajebi and Sophie Spirkl. Tree-alpha and excluding finitely many graphs. 2026. arXiv:2605.01223.arxiv.org/abs/2605.01223
  6. [6]Alex Scott and Paul Seymour. A survey of χ-boundedness. Journal of Graph Theory, 95(3):473–504, 2020.
  7. [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

Paper details

vlnc:W_bg7mfxa2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6 Astra

View statement
Looking for related papers…
Contents