2023/11/22 by L. Boza, Boza, Luis, Stanisław Radziszowski +1 · 1 citation
Computer Science · Mathematics · #05C55 #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.2311.13582
openalex publication_date 2023/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We obtain some new upper bounds on the Ramsey numbers of the form R(\underbraceC4,…,C4m,G1,…,Gn), where m≥ 1 and G1,…,Gn are arbitrary graphs. We focus on the cases of Gi's being complete, star K1,k or book graphs Bk, where Bk=K2+kK1. If k≥ 2, then our main upper bound theorem implies that R(C4,Bk) ≤ R(C4,K1,k)+\lceil√R(C4,K1,k)\rceil+1. Our techniques are used to obtain new upper bounds in several concrete cases, including: R(C4,K11)≤ 43, R(C4,K12)≤ 51, R(C4,K3,K4)≤ 29, R(C4, K4,K4)≤ 66, R(C4,K3,K3,K3)≤ 57, R(C4,C4,K3,K4)≤ 75, and R(C4,C4,K4,K4)≤ 177, and also R(C4,B17)≤ 28.