Divisible subdivisions. Issue 4 (29th July 2021)

• Record Type: Journal Article
• Authors: Alon, Noga; Krivelevich, Michael
• Is Part Of: Journal of graph theory. Volume 98:Issue 4(2021)
• Page Start: 623
• Page End: 629
• Publication Date: 2021-07-29
• Subjects: complete minors -- cycles -- divisibility -- expanders -- subdivisions; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22716
• Languages: English
• ISSNs: 0364-9024

Abstract

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.