2025/05/07 by Yanbo Zhang, Yaojun Chen, Zhang, Yanbo +1 · 5 citations
Computer Science · Mathematics · #05C55 #05D10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2505.04142
openalex publication_date 2025/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph with n vertices and n+k-2 edges and tKm denote the disjoint union of t complete graphs Km. In this paper, by developing a trichotomy for sparse graphs, we show that for given integers m≥ 2 and t≥ 1, there exists a positive constant c such that if 1≤ k≤ cn(2)/(m-1) and n is large, then G is tKm-good, that is, the Ramsey number is r(G, tKm)=(n-1)(m-1)+t . In particular, the above equality holds for any positive integers k, m, and t, provided n is large. The case t=1 was obtained by Burr, Erdős, Faudree, Rousseau, and Schelp (1980), and the case k=1 was established by Luo and Peng (2023).