2019/05/12 by József Balogh, Alexandr Kostochka, Balogh, József +5
Computer Science · Mathematics · #05C15 #05C35 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1905.04657
openalex publication_date 2019/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.