A quasi-optimal upper bound for induced paths in sparse graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918334061084672 |
|---|---|
| author | Couëtoux, Basile Defrain, Oscar Raymond, Jean-Florent |
| author_facet | Couëtoux, Basile Defrain, Oscar Raymond, Jean-Florent |
| contents | In 2012, Nešetřil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order $n$ also have an induced path of order $Ω(\log \log n)$. In this paper we give an almost matching upper bound by describing, for arbitrarily large values of $n$, 2-degenerate graphs that have a path of order $n$ and where the longest induced paths have order $O((\log \log n)^{1+o(1)})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22509 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A quasi-optimal upper bound for induced paths in sparse graphs Couëtoux, Basile Defrain, Oscar Raymond, Jean-Florent Combinatorics Discrete Mathematics In 2012, Nešetřil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order $n$ also have an induced path of order $Ω(\log \log n)$. In this paper we give an almost matching upper bound by describing, for arbitrarily large values of $n$, 2-degenerate graphs that have a path of order $n$ and where the longest induced paths have order $O((\log \log n)^{1+o(1)})$. |
| title | A quasi-optimal upper bound for induced paths in sparse graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2507.22509 |