2019/06/07 by József Balogh, Alexandr Kostochka, Balogh, József +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1906.02854
openalex publication_date 2019/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G arrows a graph H if in every 2-edge-coloring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph Kn arrows a small graph H, then every "dense" subgraph of Kn also arrows H, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large n, if n = 3t+r where r ∈ \0,1,2\ and G is an n-vertex graph with δ(G) ≥ (3n-1)/4, then for every 2-edge-coloring of G, either there are cycles of every length \3, 4, 5, …, 2t+r\ of the same color, or there are cycles of every even length \4, 6, 8, …, 2t+2\ of the same color. Our result is tight in the sense that no longer cycles (of length >2t+r) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large n, every (3t-1)-vertex graph G with minimum degree larger than 3|V(G)|/4 arrows the path P2n with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for n=3t+r where r ∈ \0,1,2\ and every n-vertex graph G with δ(G) ≥ 3n/4, in each 2-edge-coloring of G there exists a monochromatic cycle of length at least 2t+r.