2022/01/11 by Claire Hilaire, Hilaire, Claire, Jean‐Florent Raymond +1 · 1 citation
Computer Science · #05C35 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2201.03880
openalex publication_date 2022/01/11 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
In this paper we show that every graph of pathwidth less than k that has a path of order n also has an induced path of order at least (1)/(3) n1/k. This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound. This result is then used to prove the two following generalizations: - every graph of treewidth less than k that has a path of order n contains an induced path of order at least (1)/(4) (log n)1/k; - for every non-trivial graph class that is closed under topological minors there is a constant d ∈ (0,1) such that every graph from this class that has a path of order n contains an induced path of order at least (log n)d. We also describe consequences of these results beyond graph classes that are closed under topological minors.