Ramsey numbers involving a long path

详细信息    查看全文

• 作者：Chaoping Pei ; ^{peichaoping@msn.cn" class="auth_mail" title="E-mail the corresponding author} ; Yusheng Li ^{li_yusheng@tongji.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Ramsey number ; Ramsey goodness ; Long path
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：564-570
• 全文大小：450 K

文摘

Let H$H$ be a graph, and σ(H)$\sigma \left(H\right)$ the minimum size of a color class among all proper vertex-coloring of H$H$ with χ(H)$\chi \left(H\right)$ colors. A connected graph G$G$ with |G|≥σ(H)$\left|G\right|\ge \sigma \left(H\right)$ is said to be H$H$-good if R(G,H)=(χ(H)−1)(|G|−1)+σ(H)$R(G,H)=(\chi \left(H\right)-1)(\left|G\right|-1)+\sigma \left(H\right)$. In this note, we shall show that if n≥8|H|+3σ²(H)+cχ⁸(H)$n\ge 8\left|H\right|+3{\sigma }^2\left(H\right)+c{\chi }^8\left(H\right)$, then P_n$P_n$ is H$H$-good, where c=10¹⁴$c={10}^{14}$.