Planar induced paths via a decomposition into non-crossing ordered graphs
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
- A quasi-optimal upper bound for induced paths in sparse graphs
- Long induced paths in sparse graphs and graphs with forbidden patterns
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality