Long Induced Paths and Forbidden Patterns: Polylogarithmic Bounds

Abstract. Consider a graph [Formula: see text] with a long path [Formula: see text]. When is it the case that [Formula: see text] also contains a long induced path? This question has been investigated in general as well as within a number of different graph classes since the 1980s. We have recently observed in a companion paper [ Long induced paths in sparse graphs and graphs with forbidden patterns, preprint, arXiv:2411.08685, 2024] that most existing results can be recovered in a simple way by considering forbidden ordered patterns of edges along the path [Formula: see text]. In particular, we proved that if we forbid some fixed ordered matching along a path of order [Formula: see text] in a graph [Formula: see text], then [Formula: see text] must contain an induced path of order [Formula: see text]. Moreover, we completely characterized the forbidden ordered patterns forcing the existence of an induced path of polynomial size. The purpose of the present paper is to completely characterize the ordered patterns [Formula: see text] such that forbidding [Formula: see text] along a path [Formula: see text] of order [Formula: see text] implies the existence of an induced path of order [Formula: see text]. These patterns are star forests with some specific ordering, which we call constellations. As a direct consequence of our result, we show that if a graph [Formula: see text] has a path of length [Formula: see text] and does not contain [Formula: see text] as a topological minor, then [Formula: see text] contains an induced path of order [Formula: see text]. The previously best known bound was [Formula: see text] for some unspecified function [Formula: see text] depending on the Topological Minor Structure Theorem of Grohe and Marx (2015).