2024/03/20 by Lucas Wagner Ribeiro Aragão, João Pedro Marciano, Aragão, Lucas +3 · 1 citation
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical and Theoretical Analysis
paper · pdf · doi:10.48550/arxiv.2403.13742
openalex publication_date 2024/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A classical result of Chvátal implies that if n ≥ (r-1)(t-1) +1, then any colouring of the edges of Kn in red and blue contains either a monochromatic red Kr or a monochromatic blue Pt. We study a natural generalization of his result, determining the exact minimum degree condition for a graph G on n = (r - 1)(t - 1) + 1 vertices which guarantees that the same Ramsey property holds in G. In particular, using a slight generalization of a result of Haxell, we show that δ(G) ≥ n - \lceil t/2 \rceil suffices, and that this bound is best possible. We also use a classical result of Bollobás, Erdős, and Straus to prove a tight minimum degree condition in the case r = 3 for all n ≥ 2t - 1.