2025/07/16 by Chunchao Fan, Fan, Chunchao, Qizhong Lin +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2507.11835
openalex publication_date 2025/07/16 · openalex created_date 2025/10/14 · openalex updated_date 2026/08/03
A fundamental problem in graph Ramsey theory is to determine, for sparse graphs G on n vertices, the minimal n such that G is Ramsey-good for odd cycles Ck and paths Pk. Burr, Erdős, Faudree, Rousseau, and Schelp (Trans. AMS 1982) addressed this problem, establishing bounds requiring n = Ω(k10) for odd cycles and n = Ω(k12) for paths. We settle the asymptotic version of this problem, proving that these bounds are essentially tight: n = Ω(k) suffices for odd cycles and n = Ω(k2) (or n = Ω(k) under additional conditions) for paths. Specifically, we prove: (1) For odd cycles Ck (k≥3), we prove r(G, Ck) = 2n-1 for any connected n-vertex graph G satisfying the relaxed conditions n = Ω(k) and e(G) ≤ (1 + O(1/k2)) n. (2) For paths Pk (k≥2), we prove r(G, Pk) = max\ n + \lfloor k/2\rfloor - 1, n + k - 2 - α' - γ\ for any connected n-vertex graph G satisfying one of the following: (i) n = Ω(k2) and e(G) ≤ (1 + O(1/k2)) n; (ii) n = Ω(k), δ(G)≥2, α'≥ k/2, and e(G) ≤ (1 + O(1/k)) n. In the above, α' is the independence number of an appropriate subgraph of G and γ=0 if k-1 divides n+k-3-α', and γ=1 otherwise. Consequently, our results unify and generalize classical theorems on odd cycles due to Bondy and Erdős (1973), Faudree and Schelp (1974), and Rosta (1973), and on paths due to Gerencsér and Gyárfás (1967), Faudree, Lawrence, Parsons and Schelp (1974), and Parsons (1974). The proofs feature two key innovations: a novel reconstruction of the end-edge matching and an enhancement of Burr et al.'s dichotomy lemma.