Star-critical Ramsey number of versus

详细信息    查看全文

• 作者：Sh. Haghi ; ^{sh.haghi@yahoo.com} ; H.R. Maimani ^{maimani@ipm.ir} ; A. Seify ^{abbas.seify@gmail.com}
• 关键词：Ramsey number ; Star-critical ; Fan ; Complete graph
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：203-209
• 全文大小：571 K
• 卷排序：217

文摘

For two graphs GG and HH, the Ramsey number r(G,H)r(G,H) is the smallest positive integer rr, such that any red/blue coloring of the edges of graph KrKr contains either a red subgraph that is isomorphic to GG or a blue subgraph that is isomorphic to HH. Let Sk=K1,kSk=K1,k be a star of order k+1k+1 and Kn⊔SkKn⊔Sk be a graph obtained by adding a new vertex vv and joining vv to kk vertices of KnKn. The star-critical Ramsey number r∗(G,H)r∗(G,H) is the smallest positive integer kk such that any red/blue coloring of the edges of graph Kr−1⊔SkKr−1⊔Sk contains either a red subgraph that is isomorphic to GG or a blue subgraph that is isomorphic to HH where r=r(G,H)r=r(G,H). In this paper, it is shown that r∗(Fn,K4)=4n+2r∗(Fn,K4)=4n+2 where n≥4n≥4.