Long monochromatic paths and cycles in 2-colored bipartite graphs

Abstract Gyarfas and Lehel and independently Faudree and Schelp proved that in any 2-coloring of the edges of K n , n there exists a monochromatic path on at least 2 ⌈ n ∕ 2 ⌉ vertices, and this is tight. We prove a stability version of this result which holds even if the host graph is not complete; that is, for every γ ≫ η > 0 and n ≥ n 0 ( γ ) , if G is a balanced bipartite graph on 2 n vertices with minimum degree at least ( 3 ∕ 4 + γ ) n , then in every 2-coloring of the edges of G , either there exists a monochromatic cycle on at least ( 1 + η ) n vertices, or the coloring of G is close to an extremal coloring — in which case G has a monochromatic path on at least 2 ⌈ n ∕ 2 ⌉ vertices and a monochromatic cycle on at least 2 ⌊ n ∕ 2 ⌋ vertices. Furthermore, we determine an asymptotically tight bound on the length of a longest monochromatic cycle in a 2-colored balanced bipartite graph on 2 n vertices with minimum degree δ n for all 0 ≤ δ ≤ 1 .