{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}