Answers are grounded in this paper and cite their sources.
This paper demonstrates the bounds on induced paths in planar graphs, indicating potential in graph theory.
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 Ωₖ((log n/log log n)1/k ) and provide almost matching upper bounds.
No takes yet. Share an insight, caveat, or question.
Duron et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: