Thanks for the counterexample! A follow-up question: what if we ask that q is the smallest prime factor of n (and we still assume q≠p)? Can we still find counterexamples?

Per: By convex polyominoes do you mean polyominoes whose minimal bounding box has the same perimeter? That would be an interesting case to restrict to--especially because it seems more hopeful that tilings would be possible. Igor: yes, that's the number of polyominoes I meant for each n. Of course, we can also ask the question in the case of one-sided polyominoes, or fixed polyominoes, in which case there will be more.

I agree; in fact, the strict bramble number for the square grid is exactly $k$, by results in the this thesis by Josse van Dobben de Bruyn: universiteitleiden.nl/binaries/content/assets/science/mi/… Indeed, the two numbers differ by exactly 1 for any rectangular grid. My hope is that this gap is always at least 1, for graphs that have at least 2 vertices.