Excluding paths and bicliques
arXiv:2607.13995
The paper improves the known Ramsey‑type bound on the maximum length of a path in graphs that exclude a fixed path and a biclique as induced subgraphs, showing it can be taken singly exponential in a power of the clique number, and proves that for such graphs treedepth is polynomially bounded by the clique number.
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 bounding the maximum length of a path in terms of clique number . We improve the best known bound on to a function that is a singly exponential in , for some constant , which we show is best possible, up to optimizing . 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).