Long Induced Paths in Ks,s‐Free Graphs
Abstract
ABSTRACT More than 40 years ago, Galvin, Rival, and Sands showed that every ‐free graph containing an ‐vertex path must contain an induced path of length , where as . Recently, it was shown by Duron, Esperet, and Raymond that one can take . In this note, we give a short self‐contained proof that a ‐free graph with an ‐vertex path contains an induced path of length at least . Combined with the recent remarkable example of Couëtoux, Defrain, and Raymond, which provides an upper bound of , this essentially resolves this old problem.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Journal of Graph Theory
- Volume
- 112
- Issue
- 4
- Pages
- 438–441
- Publication date
- 10 April 2026
- Language
- EN