2022/02/21 by Domagoj Bradač, Lior Gishboliner, Bradač, Domagoj +3
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.2202.10388
openalex publication_date 2022/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In this paper we prove several results on Ramsey numbers R(H,F) for a fixed graph H and a large graph F, in particular for F = Kn. These results extend earlier work of Erdős, Faudree, Rousseau and Schelp and of Balister, Schelp and Simonovits on so-called Ramsey size-linear graphs. Among others, we show that if H is a subdivision of K4 with at least 6 vertices, then R(H,F) = O(v(F) + e(F)) for every graph F. We also conjecture that if H is a connected graph with e(H) - v(H) ≤ \binomk+12 - 2, then R(H,Kn) = O(nk). The case k=2 was proved by Erdős, Faudree, Rousseau and Schelp. We prove the case k=3.