Shallow brambles
arXiv:2502.04177 · doi:10.46298/dmtcs.15257
Abstract
A graph class has polynomial expansion if there is a polynomial function such that for every graph , each of the depth- minors of has average degree at most . 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 .
12 pages, final version