Sparse graphs without long induced paths - Université Clermont Auvergne Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Theory, Series B Année : 2024

Sparse graphs without long induced paths

Résumé

Graphs of bounded degeneracy are known to contain induced paths of order $\Omega(\log \log n)$ when they contain a path of order $n$, as proved by Ne\v{s}et\v{r}il and Ossona de Mendez (2012). In 2016 Esperet, Lemoine, and Maffray conjectured that this bound could be improved to $\Omega((\log n)^c)$ for some constant $c>0$ depending on the degeneracy. We disprove this conjecture by constructing, for arbitrarily large values of $n$, a graph that is 2-degenerate, has a path of order $n$, and where all induced paths have order $O((\log \log n)^2)$. We also show that the graphs we construct have linearly bounded coloring numbers.
Fichier sous embargo
Fichier sous embargo
0 4 26
Année Mois Jours
Avant la publication
dimanche 15 septembre 2024
Fichier sous embargo
dimanche 15 septembre 2024
Connectez-vous pour demander l'accès au fichier

Dates et versions

hal-04075469 , version 1 (13-03-2024)

Licence

Paternité - Pas d'utilisation commerciale - Pas de modification

Identifiants

Citer

Oscar Defrain, Jean-Florent Raymond. Sparse graphs without long induced paths. Journal of Combinatorial Theory, Series B, In press, 166, pp.30-49. ⟨10.1016/j.jctb.2023.12.003⟩. ⟨hal-04075469⟩
48 Consultations
3 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More