Ramsey numbers of paths and graphs of the same order

Chaoping Pei, Yusheng Li

Published 2014-07-26Version 1

For graphs $F_n$ and $G_n$ of order $n$, if $R(F_n, G_n)=(\chi(G_n)-1)(n-1)+\sigma(G_n)$, then $F_n$ is said to be $G_n$-good, where $\sigma(G_n)$ is the minimum size of a color class among all proper vertex-colorings of $G_n$ with $\chi(G_n)$ colors. Given $\Delta(G_n)\le \Delta$, it is shown that $P_n$ is asymptotically $G_n$-good if $\alpha(G_n)\le\frac{n}{4}$.