Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.04177 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915523284959232 |
|---|---|
| author | Bousquet, Nicolas van Batenburg, Wouter Cames Esperet, Louis Joret, Gwenaël Micek, Piotr |
| author_facet | Bousquet, Nicolas van Batenburg, Wouter Cames Esperet, Louis Joret, Gwenaël Micek, Piotr |
| contents | A graph class $\mathcal{C}$ has polynomial expansion if there is a polynomial function $f$ such that for every graph $G\in \mathcal{C}$, each of the depth-$r$ minors of $G$ has average degree at most $f(r)$. In this note, we study bounded-radius variants of some classical graph parameters such as bramble number, linkedness and well-linkedness, and we show that they are pairwise polynomially related. Furthermore, in a monotone graph class with polynomial expansion they are all uniformly bounded by a polynomial in $r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04177 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Shallow brambles Bousquet, Nicolas van Batenburg, Wouter Cames Esperet, Louis Joret, Gwenaël Micek, Piotr Combinatorics A graph class $\mathcal{C}$ has polynomial expansion if there is a polynomial function $f$ such that for every graph $G\in \mathcal{C}$, each of the depth-$r$ minors of $G$ has average degree at most $f(r)$. In this note, we study bounded-radius variants of some classical graph parameters such as bramble number, linkedness and well-linkedness, and we show that they are pairwise polynomially related. Furthermore, in a monotone graph class with polynomial expansion they are all uniformly bounded by a polynomial in $r$. |
| title | Shallow brambles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.04177 |