2025/09/22 by Julien Duron, Duron, Julien, Hugo Jacob +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2509.17835
In any graph, the maximum size of an induced path is bounded by the maximum size of a path. However, in the general case, one cannot find a converse bound, even up to an arbitrary function, as evidenced by the case of cliques. Galvin, Rival and Sands proved in 1982 that, when restricted to weakly sparse graphs, such a converse property actually holds. In this paper, we consider the maximal function f such that any planar graph (and in general, any graph of bounded genus) containing a path on n vertices contains an induced path of size f(n), and prove that f(n) ∈ Θ((log n)/(log log n)) by providing a lower bound matching the upper bound obtained by Esperet, Lemoine and Maffray, up to a constant factor. We obtain these tight bounds by analyzing graphs ordered along a Hamiltonian path that admit an edge partition into a bounded number of sets without crossing edges. In particular, we prove that when such an ordered graph can be partitioned into 2k sets of non-crossing edges, then it contains an induced path of size Ωk(((log n)/(log log n))1/k ) and provide almost matching upper bounds.