Divisible subdivisions

Noga Alon, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that for every graph (Formula presented.) of maximum degree at most 3 and for every positive integer (Formula presented.) there is a finite (Formula presented.) such that every (Formula presented.) -minor contains a subdivision of (Formula presented.) in which every edge is replaced by a path whose length is divisible by (Formula presented.). For the case of cycles we show that for (Formula presented.) every (Formula presented.) -minor contains a cycle of length divisible by (Formula presented.), and observe that this settles a recent problem of Friedman and the second author about cycles in (weakly) expanding graphs.

Original languageEnglish (US)
Pages (from-to)623-629
Number of pages7
JournalJournal of Graph Theory
Volume98
Issue number4
DOIs
StatePublished - Dec 2021

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • complete minors
  • cycles
  • divisibility
  • expanders
  • subdivisions

Fingerprint

Dive into the research topics of 'Divisible subdivisions'. Together they form a unique fingerprint.

Cite this