Tight bounds for divisible subdivisions
Journal
Journal of Combinatorial Theory. Series B
Journal Volume
165
Date Issued
2024-03-01
Author(s)
Abstract
Alon and Krivelevich proved that for every n-vertex subcubic graph H and every integer q≥2 there exists a (smallest) integer f=f(H,q) such that every Kf-minor contains a subdivision of H in which the length of every subdivision-path is divisible by q. Improving their superexponential bound, we show that [Formula presented], which is optimal up to a constant multiplicative factor.
Type
journal article