LONG INDUCED PATHS AND FORBIDDEN PATTERNS: POLYLOGARITHMIC BOUNDS

doi:10.1137/24M1720366

LONG INDUCED PATHS AND FORBIDDEN PATTERNS: POLYLOGARITHMIC BOUNDS

2026-01-01

0

PRE

AI

DOI：10.1137/24M1720366

Original

Original request for help

Save

Abstract

En 中文

Consider a graph G with a long path P. When is it the case that G 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 P. In particular, we proved that if we forbid some fixed ordered matching along a path of order n in a graph G, then G must contain an induced path of order (log n)(Omega(1)). 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 H such that forbidding H along a path P of order n implies the existence of an induced path of order (log n)(Omega(1)). 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 G has a path of length n and does not contain K-t as a topological minor, then G contains an induced path of order (log n)(Omega(1/t log2 t)). The previously best known bound was (log n)(f(t)) for some unspecified function f depending on the Topological Minor Structure Theorem of Grohe and Marx (2015).

Keywords:

unavoidable induced subgraphs

induced paths

forbidden patterns

LONG INDUCED PATHS AND FORBIDDEN PATTERNS: POLYLOGARITHMIC BOUNDS

Abstract

Journal

Organization