Ramsey Goodness of paths and unbalanced graphs

Abstract

Given graphs $G$ and $H$, we say that $G$ is $H$-$good$ if the Ramsey number $R(G,H)$ equals the trivial lower bound $(|G|-1)(\chi (H)-1)+\sigma (H)$, where $\chi (H)$ denotes the usual chromatic number of $H$, and $\sigma (H)$ denotes the minimum size of a color class in a $\chi (H)$-coloring of $H$. Pokrovskiy and Sudakov [Ramsey goodness of paths. Journal of Combinatorial Theory, Series B, 122:384-390, 2017.] proved that $P_n$ is $H$-good whenever $n\ge 4|H|$. In this paper, given $\epsilon >0$, we show that if $H$ satisfy a special unbalance condition, then $P_n$ is $H$-good whenever $n\ge (2+\epsilon )|H|$. More specifically, we show that if $m_1,\dots ,m_k$ are such that $\epsilon \cdot m_i\ge 2m_{i-1}^2$ for $2\le i\le k$, and $n\ge (2+\epsilon )(m_1+\cdots +m_k)$, then $P_n$ is $K_{m_1,\dots ,m_k}$-good.

arXiv comment10 pages, 1 figure