Abstract
Classes of graphs excluding a path and a biclique as induced subgraphs are extensively studied in the literature. One of the key structural results for such graphs is a Ramsey-type result due to Galvin, Rival, and Sands (1982), establishing the existence of a function \(f\) bounding the maximum length of a path in terms of clique number \(\omega\). We improve the best known bound on \(f\) to a function that is a singly exponential in \(\omega^c\), for some constant \(c\), which we show is best possible, up to optimizing \(c\).
Our approach also has consequences for treedepth. In particular, we show that, for graphs excluding a path and a biclique as induced subgraphs, treedepth is bounded by a polynomial function of clique number. In turn, this result implies that every hereditary graph class that admits a function bounding treedepth of graphs in the class in terms of clique number, admits a polynomial such function. This gives a treedepth analogue of a recent result on pathwidth due to Hajebi (2025).
induced path, induced biclique, longest path, clique number,
treedepth, hereditary graph class, clique-polynomiality.
05C35, 05C38, 05C75, 05C69, 05C05.
1 Introduction↩︎
Galvin, Rival, and Sands [1] in 1982 and independently Atminas, Lozin, and Razgon [2] in 2012 proved that the only reason for a graph to have a long path is the presence of a long induced path, a large clique, or a large induced biclique. Denoting by \(\omega(G)\) the clique number of \(G\) and by \(\mathop{\mathrm{\mathsf{pn}}}(G)\) the path number of \(G\), that is, the maximum number of vertices in a (not necessarily induced) path in \(G\), this result can be equivalently stated as follows.
Theorem 1 (Galvin, Rival, and Sands [1]; Atminas, Lozin, and Razgon [2]). For every two positive integers \(s\) and \(t\), there exists a function \(f\colon \mathbb{N}\to \mathbb{N}\) such that every \(\{P_s, K_{t,t}\}\)-free graph \(G\) satisfies \(\mathop{\mathrm{\mathsf{pn}}}(G)\le f(\omega(G))\).
Questions related to 1 were the subject of many recent papers, see Duron, Esperet, and Raymond [3] for an overview. The best quantitative bound known up to now is a doubly exponential function of some power of the clique number. This bound follows from the main result of Hunter, Milojević, Sudakov, and Tomon [4] (see 3).
We improve this result by showing that for graphs excluding a path and a biclique as induced subgraphs, the path number is bounded above by a singly exponential function of some power of the clique number.
theoremthmpathnumber For every two positive integers \(s\) and \(t\) there exists a positive integer \(c\) such that every \(\{P_s,K_{t,t}\}\)-free graph \(G\) satisfies \(\mathop{\mathrm{\mathsf{pn}}}(G)\le 2^{\omega(G)^c}\).
Except for optimizing the dependency of \(c\) on the excluded path and biclique, this result is best possible. Indeed, we construct examples showing that the exponential dependency on the clique number in [thm:path32number] cannot be avoided.
Our approach has consequences for treedepth, a graph parameter that plays a central role in the graph sparsity theory of Nešetřil and Ossona de Mendez [5]. We show that, for graphs excluding a path and a biclique as induced subgraphs, treedepth is bounded by a polynomial function of the clique number.
theoremthmtdbddomega For every two positive integers \(s\) and \(t\) there exists a positive integer \(c\) such that every \(\{P_s,K_{t,t}\}\)-free graph \(G\) satisfies \(\mathop{\mathrm{\mathsf{td}}}(G)\le \omega(G)^c\).
[thm:td-bdd-omega] in turn implies the treedepth analogue of a result on pathwidth due to Hajebi [6]. To state this result, we need a couple of definitions. A graph parameter is a function mapping graphs to integers that does not distinguish between isomorphic graphs. A graph class is hereditary if it is closed under vertex deletion. A graph parameter \(\rho\) is said to be clique-polynomial if the following holds: for every hereditary graph class \(\mathcal{G}\), if there exists a function \(f\) such that \(\rho(G)\le f(\omega(G))\) for every graph \(G\in \mathcal{G}\), then there exists a polynomial function \(p\) such that \(\rho(G)\le p(\omega(G))\) for every graph \(G\in \mathcal{G}\). Hajebi [6] showed that pathwidth is clique-polynomial. We show the same property for treedepth.
theoremthmpolyboundsfortreedepth For every hereditary graph class \(\mathcal{G}\), if there exists a function \(f\) such that \(\mathop{\mathrm{\mathsf{td}}}(G)\le f(\omega(G))\) for every graph \(G\in \mathcal{G}\), then there exists a polynomial function \(p\) such that \(\mathop{\mathrm{\mathsf{td}}}(G)\le p(\omega(G))\) for every graph \(G\in \mathcal{G}\).
Let us mention that analogous results do not hold for treewidth and chromatic number, as shown by Chudnovsky and Trotignon [7] and by Briański, Davies, and Walczak [8], respectively, but do hold for degeneracy in some cases, due to a result of Bourneuf, Bucić, Cook, and Davies [9] and Girão and Hunter [10]. Indeed, they showed that for every graph \(H\), there is a polynomial \(p\) such that every \(K_{t,t}\)-subgraph-free graph with no induced subdivision of \(H\) has average degree at most \(p(t)\). By Ramsey’s theorem [11], this implies that for every graph \(H\), there is a polynomial \(p\) such that every \(K_{t,t}\)-free graph with no induced subdivision of \(H\) has average degree at most \(p(\omega(G))\) and hence, degeneracy at most \(p(\omega(G))\).
A sufficient condition for a graph parameter to be clique-polynomial is that it is awesome, which is a property based on the so-called independence variants of parameters (see Bešter Štorgel et al. [12]). While several parameters, including vertex cover number, feedback vertex set number, and odd cycle transversal number, are awesome, treedepth and pathwidth are not [12]. Nonetheless, [thm:poly-bounds-for-treedepth] and the aforementioned result of Hajebi show that these two parameters satisfy a necessary condition for awesomeness, namely clique-polynomiality.
Our main results, [thm:path number,thm:td-bdd-omega], contribute to the list of results on classes of graphs excluding a path and a biclique as induced subgraphs. Such classes were extensively studied in the literature, from both structural and algorithmic points of view. For example, Kamiński and Pstrucha [13] showed that graphs excluding a path and a biclique as induced subgraphs admit finitely many subgraph-minimal obstructions to \(H\)-list-colorability (for any fixed graph \(H\)), which implies the existence of polynomial-time certifying algorithms for \(H\)-list-colorability. Dallard et al. [14] conjectured that such graphs have bounded tree-independence number, that is, they admit tree decompositions whose bags induce subgraphs of bounded independence number. Following a number of partial results (see [15]–[18]), the conjecture was proved recently in a more general context by Hajebi and Spirkl [19]. This implies that all good algorithmic properties enjoyed by graph classes with bounded tree-independence number (see [20]–[22]) hold for graphs excluding a path and a biclique as induced subgraphs. This generalizes a number of previous results (see, e.g., [23]–[25]).
The paper is structured as follows. After collecting the necessary definitions and tools in 2, we explain in 3 how to obtain a quantitative version of 1 from the main result of Hunter et al. [4]. In 4, we derive two auxiliary results regarding bounds on treedepth and path number of \(P_s\)-free graphs in terms of pathwidth. In 5, we prove [thm:path32number], while in 6, we prove [thm:td-bdd-omega] [thm:poly-bounds-for-treedepth].
2 Preliminaries↩︎
We denote by \(\mathbb{N}\) the set of all nonnegative integers. All logarithms in this paper are binary. Throughout this paper, all graphs are finite, simple, and undirected. For a graph \(G\), we denote its order, that is, the number of vertices, by \(n(G)\). For a positive integer \(n\), we denote by \(P_n\) and \(K_n\) the \(n\)-vertex path graph and the \(n\)-vertex complete graph, respectively. In this paper, a biclique \(K_{n,n}\) refers to a balanced complete bipartite graph of order \(2n\).
For a subset of vertices \(U \subseteq V(G)\) or a subgraph \(U\) of \(G\), we write \(G - U\) to denote the graph obtained from \(G\) by deleting all vertices in \(U\) and their incident edges. Given a family \(\mathcal{F}\) of graphs, we say that a graph \(G\) is \(\mathcal{F}\)-free if no induced subgraph of \(G\) is isomorphic to a member of \(\mathcal{F}\); furthermore, for a graph \(F\), we say that \(G\) is \(F\)-free if it is \(\{F\}\)-free.
For integers \(k, \ell\), we denote by \([k,\ell]\) the set of integers greater than or equal to \(k\) not exceeding \(\ell\), and set \([k]= [1,k]\).
A Hamiltonian path in a graph \(G\) is a path that visits every vertex of \(G\). A graph \(G\) is traceable if it admits a Hamiltonian path.
A path decomposition of a graph \(G\) is a sequence \((X_1, \dots, X_r)\) of subsets of \(V(G)\) called bags satisfying the following two properties:
(i) for every edge \(uv \in E(G)\), there exists an index \(i \in [r]\) such that \(\{u, v\} \subseteq X_i\), and
(ii) for every \(v\in V(G)\) there exist integers \(k,\ell\in [r]\) with \(k\le \ell\) such that for all \(j\in [r]\), we have \(v\in X_j\) if and only if \(j\in [k,\ell]\).
The width of a path decomposition is defined as \(\max_{1 \le i \le r} |X_i| - 1\). The pathwidth of \(G\), denoted by \(\mathop{\mathrm{\mathsf{pw}}}(G)\), is the minimum width over all possible path decompositions of \(G\).
A rooted tree is a tree \(T\) together with a distinguished vertex \(r \in V(T)\) called the root. A rooted forest is a disjoint union of rooted trees. The transitive closure of a rooted forest \(F\) is the graph with vertex set \(V(F)\) where two vertices are adjacent if and only if one is an ancestor of the other in \(F\). A treedepth decomposition of a graph \(G\) is a rooted forest \(F\) on the vertex set \(V(G)\) such that \(G\) is a subgraph of the transitive closure of \(F\). The depth of a rooted forest \(F\) is the maximum number of vertices on any root-to-leaf path in \(F\). The treedepth of \(G\), denoted by \(\mathop{\mathrm{\mathsf{td}}}(G)\), is the minimum depth over all treedepth decompositions of \(G\).
2.1 Tools↩︎
For easier reference, we enumerate here several standard (folklore) facts that we will use, sometimes implicitly, throughout the paper (see, e.g., [5], [26]).
Let \(G\) be a graph and \(C_1, \dots, C_k\) its connected components. Then \(\mathop{\mathrm{\mathsf{pw}}}(G) = \max_{1 \le i \le k} \mathop{\mathrm{\mathsf{pw}}}(C_i)\). Similarly, \(\mathop{\mathrm{\mathsf{td}}}(G) = \max_{1 \le i \le k} \mathop{\mathrm{\mathsf{td}}}(C_i)\) and \(\mathop{\mathrm{\mathsf{pn}}}(G) = \max_{1\le i\le k}\mathop{\mathrm{\mathsf{pn}}}(C_i)\).
Path number, pathwidth, treedepth, and clique number are all monotone under subgraphs.
Let \(G\) be a graph containing an edge, and let \(I\) be the set of isolated vertices in \(G\). Then \(\mathop{\mathrm{\mathsf{pn}}}(G)=\mathop{\mathrm{\mathsf{pn}}}(G-I)\), \(\mathop{\mathrm{\mathsf{td}}}(G)=\mathop{\mathrm{\mathsf{td}}}(G-I)\), and \(\mathop{\mathrm{\mathsf{pw}}}(G)=\mathop{\mathrm{\mathsf{pw}}}(G-I)\).
Let \(G\) be a graph with a path decomposition \((X_1,\dots,X_r)\), and let \(H\) be a connected subgraph of \(G\). Then there exist integers \(k,\ell\in [r]\) with \(\ell\le k\) such that for all \(j\in [r]\), the bag \(X_j\) intersects \(H\) if and only if \(j\in [\ell,k]\).
For every graph \(G\), every path decomposition \((X_1, \dots, X_r)\) of \(G\), and every clique \(K\) of \(G\), there exists \(i \in [r]\) such that \(K \subseteq X_i\).
Let \(G\) be a graph. Then \[\omega(G)\le \mathop{\mathrm{\mathsf{pw}}}(G)+1\le \mathop{\mathrm{\mathsf{td}}}(G) \le \mathop{\mathrm{\mathsf{pn}}}(G)\le 2^{\mathop{\mathrm{\mathsf{td}}}(G)}-1\,.\]
The following theorem is an immediate consequence of [27].
Theorem 2 (Chudnovsky, Hajebi, and Spirkl [27]). For all positive integers \(r\), \(s\), and \(t\), there exists an integer \(k\) such that every \(\{P_r, K_s, K_{t,t}\}\)-free graph has pathwidth at most \(k\).
2 also follows immediately from [1], [2] and [28].
Theorem 3 (Hajebi [6]). For every hereditary graph class \(\mathcal{G}\), if there exists a function \(f\) such that \(\mathop{\mathrm{\mathsf{pw}}}(G)\le f(\omega(G))\) for every graph \(G\in \mathcal{G}\), then there exists a polynomial function \(p\) such that \(\mathop{\mathrm{\mathsf{pw}}}(G)\le p(\omega(G))\) for every graph \(G\in \mathcal{G}\).
Corollary 1. For every two positive integers \(s\) and \(t\) there exists a positive integer \(c\) such that the following holds. Every \(\{P_s,K_{t,t}\}\)-free graph \(G\) satisfies \(\mathop{\mathrm{\mathsf{pw}}}(G) \leq {\omega(G)}^c\).
Proof. Fix positive integers \(s\) and \(t\), and let \(\mathcal{G}\) be \(\{P_s,K_{t,t}\}\)-free graphs. 2 implies that the pathwidth of every graph in \(\mathcal{G}\) is bounded by some function of its clique number. By 3, the pathwidth of every graph in \(\mathcal{G}\) is bounded by a polynomial function \(p\) of its clique number. Since a graph with \(\omega(G) = 1\) satisfies \(\mathop{\mathrm{\mathsf{pw}}}(G) = 0\), it remains to justify that there exists some positive integer \(c\) such that \(p(x)\le x^c\) for all \(x\ge 2\). Indeed, after dropping the terms with negative coefficients, we observe that \(p\) is upper-bounded by a polynomial of some degree \(d\) in which all nonzero terms have the same positive coefficient \(a\). Any such polynomial is upper bounded by a monomial of the form \(ax^{d+1}\), which in turn is bounded from above by \(x^c\) for all \(x\ge 2\), where \(c = d+1+\lceil \log a\rceil\). ◻
2.2 Transitive closures of binary trees↩︎
For a positive integer \(k\), denote by \(T^+_k\) the transitive closure of a complete binary tree of depth \(k\). See [fig:dense-tree] for an example. The family \(\{T^+_k\}_{k>0}\) will serve as a tightness example for several of our claims.
Proposition 4. Let \(k\) be a positive integer. Then:
For \(k>1\), the graph \(T^+_k\) is isomorphic to the graph obtained from the disjoint union of two copies of \(T^+_{k-1}\) by adding a universal vertex.
\(T^+_k\) is traceable, that is, \(\mathop{\mathrm{\mathsf{pn}}}(T^+_k) = |V(T^+_k)| = 2^{k}-1\).
\(T^+_k\) is \(\{P_4,K_{2,2}\}\)-free.
\(\omega(T_k^+)=\mathop{\mathrm{\mathsf{pw}}}(T_k^+) + 1 = \mathop{\mathrm{\mathsf{td}}}(T^+_k) = k\).
Proof. For completeness we offer short proofs in turn.
Immediate from the definition and the fact that for \(k>1\), the complete binary tree of depth \(k\) is obtained from the disjoint union of two complete binary trees of depth \(k-1\) by adding a new vertex as a root and making it adjacent to the roots of the two smaller trees.
By induction on \(k\). For \(k>1\), due to [P-inductive-def], the root \(r\) of \(T^+_k\) is adjacent to all vertices in its left and right subtrees, both of which are isomorphic to \(T^+_{k-1}\). Concatenating a Hamiltonian path of the left subtree, the root \(r\), and a Hamiltonian path of the right subtree yields a Hamiltonian path of \(T^+_k\).
By induction on \(k\), using [P-inductive-def] and the fact that the operations of disjoint union and addition of a universal vertex preserve \(\{P_4,K_{2,2}\}\)-freeness.
By [treedepth-path-number], it suffices to show that \(\mathop{\mathrm{\mathsf{td}}}(T^+_k) \le k \le \omega(T^+_k)\). The former inequality follows from the fact that the underlying binary tree of depth \(k\) is a valid treedepth decomposition. For the latter one, observe that any root-to-leaf path in the underlying binary tree of depth \(k\) forms a clique of size \(k\) in \(T^+_k\).
◻
3 Comparison with Hunter et al. ↩︎
The main result of Hunter et al. [4] hides the dependency on the size of the excluded biclique in the \(\Omega(\cdot)\) notation. The variant below can be obtained from the proof.
Theorem 5. Let \(G\) be a \(K_{r,r}\)-subgraph-free graph containing a path on \(n\) vertices, where \(n\geq r\geq 2\). Then \(G\) contains an induced path of length at least \(\Omega \big(\frac{\log \log n}{r\log\log\log n}\big)\).
We now explain why 5 leads to a quantitative variant of 1 establishing a doubly exponential bound on the path number in terms of some power of the clique number.
Theorem 6. For every two positive integers \(s\) and \(t\) there exists a positive integer \(c\) such that every \(\{P_s,K_{t,t}\}\)-free graph \(G\) satisfies \(\mathop{\mathrm{\mathsf{pn}}}(G)<2^{2^{(\omega(G)+1)^c}}\).
Proof. 5 implies that there exists a positive integer \(a\) such that for every \(n\ge r\ge 2\), every graph \(G\) that does not contain \(K_{r,r}\) as a subgraph, and which contains a path on \(n\) vertices, contains an induced path of length at least \(a(\log\log n)^{0.99}/r\).
Fix \(s\) and \(t\) and let \(G\) be a \(\{P_s,K_{t,t}\}\)-free graph. Let \(r = (\omega(G)+1)^t\). Since \(G\) is \(K_{t,t}\)-free, it does not contain \(K_{r,r}\) as a subgraph. Indeed, if \(G\) contains a \(K_{r,r}\), with parts \(A\) and \(B\), then at least one of the two parts, say \(A\), has independence number less than \(t\), but then \(G[A]\) would have to contain a clique of size \(\omega(G)+1\), a contradiction. Here we are using the bound of Erdös and Szekeres [29] that every graph on at least \(\binom{s+t-2}{t-1}\) vertices contains either a clique of size \(s\) or a stable set of size \(t\), and the observation that \(\binom{s+t-2}{t-1} \leq \binom{s+t-1}{t} \leq s^t\).
We claim that \(\mathop{\mathrm{\mathsf{pn}}}(G)< 2^{2^{(\omega(G)+1)^c}}\) where \(c\) is any integer satisfying \[{c \ge (t+ \log s - \log a)/0.99}\,.\] Suppose for a contradiction that \(G\) contains a path on \(n\) vertices, where \[n\ge 2^{2^{(\omega(G)+1)^c}}\,.\] By assumption, \(G\) contains an induced path on at least \(a(\log\log n)^{0.99}/r\) vertices. The inequality \(n\ge 2^{2^{(\omega(G)+1)^c}}\) yields \({\log\log n \ge (\omega(G)+1)^c}\), and consequently \[\begin{align} a\frac{(\log\log n)^{0.99}}{r} &\ge a\frac{(\omega(G)+1)^{0.99c}}{r}\\ &= a(\omega(G)+1)^{0.99c-t}\\ & \ge a2^{0.99c-t} \ge s\,. \end{align}\] Hence, \(G\) contains an induced path on \(s\) vertices, a contradiction. ◻
4 Harnessing path decompositions↩︎
In this section, we bound treedepth and path number of \(P_s\)-free graphs in terms of pathwidth. We start by proving a linear relationship between treedepth and pathwidth.
Theorem 7. Let \(s\ge 3\) be an integer and let \(G\) be \(P_s\)-free graph with at least one edge. Then \(\mathop{\mathrm{\mathsf{td}}}(G) \leq (s-1)\cdot \mathop{\mathrm{\mathsf{pw}}}(G)\).
Proof. First observe that the inequality holds for graphs with \(\mathop{\mathrm{\mathsf{pw}}}(G)=1\). Indeed, if \(\mathop{\mathrm{\mathsf{pw}}}(G)=1\), then \(G\) is a forest, so \(\mathop{\mathrm{\mathsf{pn}}}(G) < s\) and [treedepth-path-number] implies \[\mathop{\mathrm{\mathsf{td}}}(G) \le \mathop{\mathrm{\mathsf{pn}}}(G)\le (s-1)\mathop{\mathrm{\mathsf{pw}}}(G)\,.\] The proof for the general case is by induction on \(n(G)\). If \(n(G)= 2\), we are done since \(\mathop{\mathrm{\mathsf{pw}}}(G)=1\).
For the rest of the proof let \(n(G) \ge 3\) and \(\mathop{\mathrm{\mathsf{pw}}}(G)\ge 2\). Suppose first that \(G\) is disconnected. Denote by \(I\) the set of isolated vertices in \(G\), and let \(G_1,\ldots, G_k\) for some \(k\ge 1\) be the non-trivial components of \(G\). Then, the induction hypothesis yields \(\mathop{\mathrm{\mathsf{td}}}(G_i) \leq (s-1) \mathop{\mathrm{\mathsf{pw}}}(G_i)\) for each \(i\in [k]\). Hence, by [obs:components] and [fct:ignoreIsolates], we obtain \[\begin{align} \mathop{\mathrm{\mathsf{td}}}(G) &= \mathop{\mathrm{\mathsf{td}}}(G-I) = \max_{1\le i\le k}\mathop{\mathrm{\mathsf{td}}}(G_i)\\ &\le (s-1) \left(\max_{1\le i\le k}\mathop{\mathrm{\mathsf{pw}}}(G_i)\right) \\[2mm] &= (s-1)\mathop{\mathrm{\mathsf{pw}}}(G-I) = (s-1)\mathop{\mathrm{\mathsf{pw}}}(G)\,, \end{align}\] as desired.
We may therefore assume that \(G\) is connected. Let \((X_1, \dots, X_m)\) be a path decomposition of \(G\) of width \(\mathop{\mathrm{\mathsf{pw}}}(G)\). Let \(a_1 \in X_1\) and \(a_m \in X_m\), and let \(P\) be a shortest path in \(G\) from \(a_1\) to \(a_m\). Since \(P\) is an induced path and \(G\) is \(P_s\)-free, \(|V(P)| \le s-1\). Furthermore, [fct:subgraph-interval] implies that \(V(P) \cap X_i \neq \emptyset\) for every \(i \in [m]\). It follows that \(\mathop{\mathrm{\mathsf{pw}}}(G - P) \le \mathop{\mathrm{\mathsf{pw}}}(G)-1\). Let \(F\) be a treedepth decomposition of \(G- P\) with depth equal to \(\mathop{\mathrm{\mathsf{td}}}(G- P)\) and let \(R\) be the set of roots of \(F\). Let \(T\) be the tree obtained from the disjoint union of \(F\) and \(P\) by adding an edge between \(a_m\) and every vertex in \(R\), and let \(a_1\) be the root of \(T\). Then, \(T\) is a treedepth decomposition of \(G\) with depth at most \(\mathop{\mathrm{\mathsf{td}}}(G - P)+(s-1)\), implying that \(\mathop{\mathrm{\mathsf{td}}}(G) \leq \mathop{\mathrm{\mathsf{td}}}(G - P)+(s-1)\).
If \(G-P\) has at least one edge, then the induction hypothesis implies that \(\mathop{\mathrm{\mathsf{td}}}(G- P) \leq (s-1)(\mathop{\mathrm{\mathsf{pw}}}(G)-1)\), and thus \[\mathop{\mathrm{\mathsf{td}}}(G) \leq \mathop{\mathrm{\mathsf{td}}}(G - P)+(s-1) \leq (s-1)\mathop{\mathrm{\mathsf{pw}}}(G)\,,\] as desired. We may thus assume that \(G-P\) is edgeless. Then, \({\mathop{\mathrm{\mathsf{td}}}(G - P)\le 1}\) and, since \(\mathop{\mathrm{\mathsf{pw}}}(G)\ge 2\) and \(s\ge 3\), we obtain that \[\mathop{\mathrm{\mathsf{td}}}(G) \leq \mathop{\mathrm{\mathsf{td}}}(G - P)+(s-1) \leq s \le (s-1)\mathop{\mathrm{\mathsf{pw}}}(G)\,,\] as desired. ◻
7 and the inequality \(\mathop{\mathrm{\mathsf{pn}}}(G)\le 2^{\mathop{\mathrm{\mathsf{td}}}(G)}-1\) (see [treedepth-path-number]) imply that for every integer \(s\ge 3\), every \(P_s\)-free graph with at least one edge satisfies \[\mathop{\mathrm{\mathsf{pn}}}(G) \le 2^{(s-1)\mathop{\mathrm{\mathsf{pw}}}(G)}-1\,.\] We recently learned of a better bound, obtained by a similar approach as the one used in the proof of 7, due to Hilaire and Raymond in [30]: for every integer \(s\ge 3\), every \(P_s\)-free graph with at least one edge satisfies \[\mathop{\mathrm{\mathsf{pn}}}(G) \le (3s-3)^{\mathop{\mathrm{\mathsf{pw}}}(G)+1}\,.\] Using a similar strategy, we obtain a further improvement, as follows.
Theorem 8. Let \(s\ge 3\) be an integer and let \(G\) be \(P_s\)-free graph with at least one edge. Then \[\mathop{\mathrm{\mathsf{pn}}}(G) \leq s^{\mathop{\mathrm{\mathsf{pw}}}(G)}-1\,.\]
Proof. We again start by verifying that, in the case \(\mathop{\mathrm{\mathsf{pw}}}(G)=1\), we have a forest and the fact \({\mathop{\mathrm{\mathsf{pn}}}(G)<s}\) implies our claim. We proceed by induction on \(n(G)\) where the base case (i.e., \(n(G)=2\)) is settled due to \(\mathop{\mathrm{\mathsf{pw}}}(K_2)=1\).
Suppose now that \(n(G) \ge 3\). Consider first the case where \(G\) is disconnected. Denote by \(I\) the set of isolated vertices in \(G\) and again recall [fct:ignoreIsolates], in particular, \(\mathop{\mathrm{\mathsf{pw}}}(G)=\mathop{\mathrm{\mathsf{pw}}}(G-I)\) and \(\mathop{\mathrm{\mathsf{pn}}}(G)=\mathop{\mathrm{\mathsf{pn}}}(G-I)\). Denote by \(G_1,\ldots, G_k\) the non-trivial components of \(G\), and observe by the induction hypothesis that \(\mathop{\mathrm{\mathsf{pn}}}(G_i) \leq s^{\mathop{\mathrm{\mathsf{pw}}}(G_i)}-1\) for each \(i\in [k]\). By [obs:components], we thus obtain \[\begin{align} \mathop{\mathrm{\mathsf{pn}}}(G) &= \mathop{\mathrm{\mathsf{pn}}}(G-I) = \max_{1\le i\le k}\mathop{\mathrm{\mathsf{pn}}}(G_i)\\ &\le s^{\max_{1\le i\le k}\mathop{\mathrm{\mathsf{pw}}}(G_i)}-1\\[2mm] &= s^{\mathop{\mathrm{\mathsf{pw}}}(G-I)}-1 = s^{\mathop{\mathrm{\mathsf{pw}}}(G)}-1\,, \end{align}\] as desired.
Suppose now that \(G\) is connected, let \((X_1, \dots, X_m)\) be a path decomposition of \(G\) realizing \(\mathop{\mathrm{\mathsf{pw}}}(G)\), and let \(P\) be a shortest path connecting some vertex of \(X_1\) with some vertex of \(X_m\). We again have and \(P \cap X_i \neq \emptyset\) for every \(i \in \{1, \dots, m\}\), and also \(|V(P)| < s\), since \(G\) is \(P_s\)-free. In particular, \(\mathop{\mathrm{\mathsf{pw}}}(G - P) \le \mathop{\mathrm{\mathsf{pw}}}(G) - 1\). Note that we may assume that \(G-P\) has at least one vertex, since otherwise \(G\) is a path and has pathwidth \(1\).
Let \(C_1,\dots,C_{\ell}\) be the connected components of \(G-P\). Let \(Q\) be a path in \(G\). Consider how \(Q\) alternates between vertices of \(P\) and the connected components of \(C_1, \dots, C_l\). Since \(P\) contributes at most \(s-1\) vertices to \(Q\), the path \(Q\) can traverse at most \(s\) such components of \(G-P\). Therefore, we can bound \(\mathop{\mathrm{\mathsf{pn}}}(G)\) by \[\mathop{\mathrm{\mathsf{pn}}}(G) \le s \cdot \max_{i\in [\ell]} \mathop{\mathrm{\mathsf{pn}}}(C_i) + (s - 1) \le s \cdot \mathop{\mathrm{\mathsf{pn}}}(G - P) + s - 1\,.\] If \(G - P\) is edgeless, then \(\mathop{\mathrm{\mathsf{pn}}}(G - P)=1\), which implies \(\mathop{\mathrm{\mathsf{pn}}}(G)\le 2s- 1\le s^{\mathop{\mathrm{\mathsf{pw}}}(G)}-1\) due to \(\mathop{\mathrm{\mathsf{pw}}}(G)\ge 2\) and \(s\ge 3\). Otherwise, the induction hypothesis on \(G-P\) and the fact that \(\mathop{\mathrm{\mathsf{pw}}}(G - P) \le \mathop{\mathrm{\mathsf{pw}}}(G) - 1\) imply that \[\begin{align} \mathop{\mathrm{\mathsf{pn}}}(G)&\le s \left( \left( s^{\mathop{\mathrm{\mathsf{pw}}}(G)-1} - 1 \right) + 1 \right) - 1 = s^{\mathop{\mathrm{\mathsf{pw}}}(G)} - 1, \end{align}\] as desired. ◻
We observe that exponential dependence on the pathwidth cannot be avoided due to, for instance, transitive closures of binary trees which are \(P_4\)-free (also see [fig:dense-tree]). Indeed, for any positive integer \(k\), we have \(\mathop{\mathrm{\mathsf{pw}}}(T^+_k)=k\) while \(\mathop{\mathrm{\mathsf{pn}}}(T^+_k)=2^{k+1}-1\) (see 4).
Remark 1. The aforementioned result in [30] is stated as:
For every positive integer \(k\), if \(G\) is a graph with pathwidth less than \(k\) that has a path of order \(n\), then \(G\) has an induced path of order at least \(\frac{1}{3}n^{1/k}\).
8 leads to the following improved bound:
For every integer \(k\ge 2\), if \(G\) is a graph with pathwidth less than \(k\) that has a path of order \(n\), then \(G\) has an induced path of order at least \((n+1)^{1/(k-1)}-1\).
5 Improving a Ramsey-type result↩︎
Using the exponential relationship between the path number of a \(P_s\)-free graph and its pathwidth given by 8, we now derive one of our main results, the following quantitative improvement of 1.
Proof. Fix two positive integers \(s\) and \(t\). We may assume that \(s\ge 2\). By 1, there exists a positive integer \(d\) such that every \(\{P_s,K_{t,t}\}\)-free graph \(G\) satisfies \(\mathop{\mathrm{\mathsf{pw}}}(G) \leq {\omega(G)}^d\). Let \(G\) be a \(\{P_s,K_{t,t}\}\)-free graph. We may assume that \(\omega(G)\ge 2\), since otherwise \(\mathop{\mathrm{\mathsf{pn}}}(G)\le 1\le 2^{{\omega(G)}^c}\) for every integer \(c\). Note that \(s\ge 3\), since \(G\) is \(P_s\)-free but has at least one edge. Hence, by 8, \(\mathop{\mathrm{\mathsf{pn}}}(G) \leq s^{\mathop{\mathrm{\mathsf{pw}}}(G)}\). Let \(c= d+\lceil\log\log s\rceil\). Then \(\log s\le 2^{c-d}\le {\omega(G)}^{c-d}\) and hence, \((\log s)\cdot {\omega(G)}^d\le {\omega(G)}^c\), which together with the inequality \({\mathop{\mathrm{\mathsf{pw}}}(G) \leq {\omega(G)}^d}\) implies \[\mathop{\mathrm{\mathsf{pn}}}(G) \leq s^{\mathop{\mathrm{\mathsf{pw}}}(G)} \leq s^{{\omega(G)}^d} \leq 2^{(\log s)\cdot {\omega(G)}^d}\le 2^{{\omega(G)}^c}\,,\] as desired. ◻
Exponential dependence on the clique number cannot be avoided, e.g., due to the family of transitive closures of binary trees \(\{T^+_k\}_{k>0}\) (also see [fig:dense-tree]), where \(\omega(T^+_k)=k\) while \(\mathop{\mathrm{\mathsf{pn}}}(T^+_k)=2^{k+1}-1\) by 4. Furthermore, the constant \(c\) must depend on \(s\) and \(t\), as can be seen, for instance, by looking at the family of path graphs.
6 Treedepth is clique-polynomial↩︎
In what follows, we make use of the other main result from 4, the linear relationship between treedepth and pathwidth for \(P_s\)-free graphs given by 7, to prove [thm:td-bdd-omega].
Proof. Fix \(s\) and \(t\). By 1, there exists a positive integer \(d\) such that \({\mathop{\mathrm{\mathsf{pw}}}(G) \leq {\omega(G)}^d}\), where \(G\) is an arbitrary \(\{P_s,K_{t,t}\}\)-free graph. We may assume that \(G\) has at least one edge, since otherwise \(\mathop{\mathrm{\mathsf{td}}}(G)\le \omega(G)^d\). Note that \(s\ge 3\), since \(G\) is \(P_s\)-free but has at least one edge. Hence, 7 implies that \({\mathop{\mathrm{\mathsf{td}}}(G) \leq (s-1)\cdot \mathop{\mathrm{\mathsf{pw}}}(G)}\). Since \(\mathop{\mathrm{\mathsf{pw}}}(G) \leq {\omega(G)}^d\), we obtain that \({\mathop{\mathrm{\mathsf{td}}}(G) \leq (s-1)\cdot {\omega(G)}^d}\). Similarly as in the proof of 1, we conclude that there exists a positive integer \(c\) depending only on \(s\) and \(d\) (and hence, only on \(s\) and \(t\)) such that \(\mathop{\mathrm{\mathsf{td}}}(G)\le \omega(G)^c\), as desired. ◻
Finally, we derive from [thm:td-bdd-omega] the analogue of 3 for treedepth, that is, we show that treedepth is clique-polynomial.
Proof. By [thm:td-bdd-omega] it is enough to prove that every graph in \(\mathcal{G}\) is \(\{P_s,K_{t,t}\}\)-free. To this end let \(\mathcal{G}\) be a \((\mathop{\mathrm{\mathsf{td}}},\omega)\)-bounded graph class. Fix a function \(f\colon \mathbb{N}\to \mathbb{N}\) such that \(\mathop{\mathrm{\mathsf{td}}}(G)\le f(\omega(G))\) for all graphs \(G\in \mathcal{G}\). We may assume that \(f\) is non-decreasing, since otherwise we could redefine \(f(k)\) for \(k\in \mathbb{N}\) by setting it to \(\max_{i\in [k]}f(i)\). Let \(s = t = 2^{f(2)}\). We claim that \(\mathcal{G}\) excludes \(P_s\). Suppose for a contradiction that \(P_s\in \mathcal{G}\). Since \(\omega(P_s) \le 2\) and \(f\) is non-decreasing, we have that \(\mathop{\mathrm{\mathsf{td}}}(P_s)\le f(2)\). By [treedepth-path-number], it holds that \(s = \mathop{\mathrm{\mathsf{pn}}}(P_s)\le 2^{f(2)}-1\), a contradiction. Furthermore, we claim that \(\mathcal{G}\) excludes \(K_{t,t}\). Suppose for a contradiction that \(K_{t,t}\in \mathcal{G}\). Since \(\omega(K_{t,t}) = 2\), we have that \(\mathop{\mathrm{\mathsf{td}}}(K_{t,t})\le f(2)\). Then, [treedepth-path-number] implies that \(2^{f(2)+1} = 2t = \mathop{\mathrm{\mathsf{pn}}}(K_{t,t})\le 2^{f(2)}-1\), a contradiction. Since \(\mathcal{G}\) is hereditary, every graph in \(\mathcal{G}\) is \(\{P_s,K_{t,t}\}\)-free, as desired. ◻
References↩︎
M. C. was supported by NSF Grant DMS-2348219, NSF Grant CCF-2505100, AFOSR grant FA9550-25-1-0275 and a Guggenheim Fellowship. J. C. was supported by NSF Grant DMS-2348219, NSF Grant CCF-2505100, AFOSR grant FA9550-25-1-0275, and by the Fonds de recherche du Québec Grant 321124. M. K. was supported in part by the Slovenian Research and Innovation Agency (research program P1-0383 and research project N1-0370). M. M. was supported in part by the Slovenian Research and Innovation Agency (I0-0035, research program P1-0285 and research projects J1-60012, J1-70035, J1-70046, and N1-0370).↩︎