EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Long Induced Paths in Ks,s‐Free Graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov, István Tomon

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →