Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Shallow brambles
Article

Shallow brambles

Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, Piotr Micek
Download article
Open on arXiv
Submitted on
February 19, 2025
Accepted on
September 9, 2025
Published on
September 17, 2025
Last modified on
September 17, 2025
Volume 27
vol. 27:3
Graph Theory
DOI
10.46298/dmtcs.15257
License
Attribution 4.0 International (CC BY 4.0)
Indicators
815
Views
539
Downloads

Shallow brambles

Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, Piotr Micek
Abstract
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$. 12 pages, final version
Keywords
  • Combinatorics
Mathematics Subject Classification 2020
  • 05C15 - Coloring of graphs and hypergraphs
  • 05C42 - Density (toughness, etc.)
Preview
Loading PDF preview...