Long Induced Paths in Ks,s‐Free Graphs
Journal of Graph Theory · 2026-08 · 112 (4) · 438-441
DOI: 10.1002/jgt.70040 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 10.04.2026. Verfasst von Zach Hunter und 3 weiteren Autor:innen. Die Arbeit nennt 11 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung, Svenska Forskningsrådet Formas.
Abstract (Originalsprache)
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.
Förderung
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Svenska Forskningsrådet Formas
Zitieren
APA
Hunter, Z., Milojević, A., Sudakov, B., & Tomon, I. (2026). Long Induced Paths in Ks,s‐Free Graphs. Journal of Graph Theory, 112(4), 438-441. https://doi.org/10.1002/jgt.70040
Vancouver
Hunter Z, Milojević A, Sudakov B, Tomon I. Long Induced Paths in Ks,s‐Free Graphs. Journal of Graph Theory. 2026;112(4):438-441. doi:10.1002/jgt.70040
BibTeX
@article{Hunter2026,
author = {Hunter, Zach and Milojević, Aleksa and Sudakov, Benny and Tomon, István},
title = {Long Induced Paths in Ks,s‐Free Graphs},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {4},
pages = {438--441},
doi = {10.1002/jgt.70040}
}
EUVIMED