2024/12/19 by Duron, Julien, Esperet, Louis, Raymond, Jean-Florent · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.14863
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 80s. We have recently observed in a companion paper (Long induced paths in sparse graphs and graphs with forbidden patterns, arXiv:2411.08685, 2024) that most existing results can 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)Ω(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)Ω(1). These patterns are star forests with some specific ordering, which we called 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 Kt as a topological minor, then G contains an induced path of order (log n)Ω(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).