Id: arxiv/2607.13995 Url: https://arxiv.org/abs/2607.13995 Tags: math.CO, cs.DM Score: 0 Title: Excluding paths and bicliques Domain: math.CO Source: arxiv Authors: Maria Chudnovsky, Julien Codsi, Matjaž Krnc, Martin Milanič Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-15 Page: https://delphi.science/r/arxiv/2607.13995 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 $ω$. We improve the best known bound on $f$ to a function that is a singly exponential in $ω^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…