کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419491 | 683823 | 2011 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Star-critical Ramsey numbers Star-critical Ramsey numbers](/preview/png/419491.png)
The graph Ramsey number R(G,H)R(G,H) is the smallest integer rr such that every 2-coloring of the edges of KrKr contains either a red copy of GG or a blue copy of HH. We find the largest star that can be removed from KrKr such that the underlying graph is still forced to have a red GG or a blue HH. Thus, we introduce the star-critical Ramsey number r∗(G,H)r∗(G,H) as the smallest integer kk such that every 2-coloring of the edges of Kr−K1,r−1−kKr−K1,r−1−k contains either a red copy of GG or a blue copy of HH. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K2K2 and K3K3, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(Tn,Km)R(Tn,Km), R(nK2,mK2)R(nK2,mK2) and R(Pn,C4)R(Pn,C4).
Journal: Discrete Applied Mathematics - Volume 159, Issue 5, 6 March 2011, Pages 328–334