Tight bound on treedepth in terms of pathwidth and longest path
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929572381982720 |
|---|---|
| author | Hatzel, Meike Joret, Gwenaël Micek, Piotr Pilipczuk, Marcin Ueckerdt, Torsten Walczak, Bartosz |
| author_facet | Hatzel, Meike Joret, Gwenaël Micek, Piotr Pilipczuk, Marcin Ueckerdt, Torsten Walczak, Bartosz |
| contents | We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^b$ vertices as a subgraph has treedepth at most $10ab$. The bound is best possible up to a constant factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_02995 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tight bound on treedepth in terms of pathwidth and longest path Hatzel, Meike Joret, Gwenaël Micek, Piotr Pilipczuk, Marcin Ueckerdt, Torsten Walczak, Bartosz Combinatorics Discrete Mathematics We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^b$ vertices as a subgraph has treedepth at most $10ab$. The bound is best possible up to a constant factor. |
| title | Tight bound on treedepth in terms of pathwidth and longest path |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2302.02995 |