Divisible subdivisions. Issue 4 (29th July 2021) - Alon, Noga; Krivelevich, Michael
Abstract: We prove that for every graph H of maximum degree at most 3 and for every positive integer q there is a finite f = f ( H, q ) such that every K f ‐minor contains a subdivision of H in which every edge is replaced by a path whose length is divisible by q . For the case of cycles we show that for f = O ( q log q ) every K f ‐minor contains a cycle of length divisible by q, and observe that this settles a recent problem of Friedman and the second author about cycles in (weakly) expanding graphs.