2024/11/13 by Julien Duron, Duron, Julien, Louis Esperet +3 · 3 citations
Computer Science · #Advanced Graph Theory Research #Cellular Automata and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2411.08685
openalex publication_date 2024/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Consider a graph G with a path P of order n. What conditions force G to also have a long induced path? As complete bipartite graphs have long paths but no long induced paths, a natural restriction is to forbid some fixed complete bipartite graph Kt,t as a subgraph. In this case we show that G has an induced path of order (log log n)1/5-o(1). This is an exponential improvement over a result of Galvin, Rival, and Sands (1982) and comes close to a recent upper bound of order O((log log n)2). Another way to approach this problem is by viewing G as an ordered graph (where the vertices are ordered according to their position on the path P). From this point of view it is most natural to consider which ordered subgraphs need to be forbidden in order to force the existence of a long induced path. Focusing on the exclusion of ordered matchings, we improve or recover a number of existing results with much simpler proofs, in a unified way. We also show that if some forbidden ordered subgraph forces the existence of a long induced path in G, then this induced path has size at least Ω((log log log n)1/3), and can be chosen to be increasing with respect to P.