Planar induced paths via a decomposition into non-crossing ordered graphs

arXiv:2509.17835 · math.CO, cs.DM · Submitted 2025-09-22 · Read on arXiv

math.CO, cs.DM

Submitted: 2025-09-22

Updated: 2026-10-31

License: http://creativecommons.org/licenses/by/4.0/

The gist: In any graph, the maximum size of an induced path is bounded by the maximum size of a path.

Terminology

Abstract

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) in Θ(n/ 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 the guaranteed size of an induced path when the ordered graph can be partitioned into 2k, resp. 2k+1, sets of non-crossing edges, is Θ k((n/ n) 1/k), resp. Θ k((n) 1/(k + 1)).

Sources

Related papers