Long monochromatic paths and cycles in 2-edge-colored multipartite graphs

József Balogh, Alexandr Kostochka, Mikhail Lavrov, Xujun Liu

Research output: Contribution to journalArticle

Abstract

We solve four similar problems: for every fixed s and large n, we describe all values of n1, …, ns such that for every 2-edge-coloring of the complete s-partite graph Kn1,…,ns there exists a monochromatic (i) cycle C2n with 2n vertices, (ii) cycle C≥2n with at least 2n vertices, (iii) path P2n with 2n vertices, and (iv) path P2n+1 with 2n + 1 vertices. This implies a generalization for large n of the conjecture by Gyárfás, Ruszinkó, Sárközy and Szemerédi that for every 2-edge-coloring of the complete 3-partite graph Kn,n,n there is a monochromatic path P2n+1 . An important tool is our recent stability theorem on monochromatic connected matchings.

Original languageEnglish (US)
Pages (from-to)55-100
Number of pages46
JournalMoscow Journal of Combinatorics and Number Theory
Volume9
Issue number1
DOIs
StatePublished - Jan 1 2020

Keywords

  • Paths and cycles
  • Ramsey number
  • Regularity Lemma

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Long monochromatic paths and cycles in 2-edge-colored multipartite graphs'. Together they form a unique fingerprint.

  • Cite this