2019/01/15 by Chula J. Jayawardene, Jayawardene, Chula J.
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1901.04802
Let G, H and K represent three graphs without loops or parallel edges and n represent an integer. Given any red blue coloring of the edges of G, we say that K → (G,H), if there exists red copy of G in K or a blue copy of H in K. Let Kn represent a complete graph on n vertices, Cn a cycle on n vertices and Sn=K1,n a star on n+1 vertices. The Ramsey number r(G, H) is defined as min\n | Kn→ (G,H)\. Likewise, the star-critical Ramsey number r_*(H, G) is defined min\k | Kr(G,H)-1 \sqcup K1,k → (H, G) \. When n >3, in this paper we show that r_*(Cn,K5)=3n-1 except r_*(C4,K5)=13. We also characterize all Ramsey critical r(Cn,K5) graphs.