Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Long induced paths in Ks,s-free graphs
Department of Mathematics, ETH Zürich, Zürich, Switzerland.
Department of Mathematics, ETH Zürich, Zürich, Switzerland.
Department of Mathematics, ETH Zürich, Zürich, Switzerland.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8344-3592
2026 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118Article in journal (Refereed) Epub ahead of print
Abstract [en]

More than 40 years ago, Galvin, Rival, and Sands showed that every Ks,s-free graph containing an n-vertex path must contain an induced path of length f(n), where f(n)→∞ as n→∞. Recently, it was shown by Duron, Esperet, and Raymond that one can take f(n) = (log log n)1/5-o(1). In this note, we give a short self-contained proof that a Ks,s-free graph with an n-vertex path contains an induced path of length at least (log log n)1-o(1). Combined with the recent remarkable example of Couëtoux, Defrain, and Raymond, which provides an upper bound of O((log log n)1+o(1)), this essentially resolves this old problem.

Place, publisher, year, edition, pages
John Wiley & Sons, 2026.
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-252370DOI: 10.1002/jgt.70040ISI: 001736640900001Scopus ID: 2-s2.0-105035286492OAI: oai:DiVA.org:umu-252370DiVA, id: diva2:2056313
Available from: 2026-04-28 Created: 2026-04-28 Last updated: 2026-04-28

Open Access in DiVA

fulltext(859 kB)73 downloads
File information
File name FULLTEXT01.pdfFile size 859 kBChecksum SHA-512
25b3f4ec2f657890ffddd81258c6d4027be66c6d31d31ecf1d55527af0e786fa9deb0d600a8f08225d16b1d124a038d46540fa25f59d9c0b0f3e9ca608c59fd5
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Tomon, István

Search in DiVA

By author/editor
Tomon, István
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Graph Theory
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 112 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf