Nicolas Bousquet ; Wouter Cames van Batenburg ; Louis Esperet ; Gwenaël Joret ; Piotr Micek - Shallow brambles

dmtcs:15257 - Discrete Mathematics & Theoretical Computer Science, September 17, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.15257
Shallow bramblesArticle

Authors: Nicolas Bousquet ; Wouter Cames van Batenburg ; Louis Esperet ; Gwenaël Joret ; Piotr Micek

    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


    Volume: vol. 27:3
    Section: Graph Theory
    Published on: September 17, 2025
    Accepted on: September 9, 2025
    Submitted on: February 19, 2025
    Keywords: Combinatorics

    Consultation statistics

    This page has been seen 297 times.
    This article's PDF has been downloaded 148 times.