An exact Ramsey number of large bipartite graphs versus odd wheel

Abstract

The Ramsey number for the pair of graphs ${\mathbb{K}}_{1,n}$ (star) versus $W_m$ (wheel) has been extensively studied. In contrast, the Ramsey number of ${\mathbb{K}}_{2,n}$ versus the wheel is not yet explored due to the bit more structural complexity of ${\mathbb{K}}_{2,n}$ compared to the star. In this article, we have established an exact value of ${\mathbb{K}}_{2,n}$ versus $W_m$ for large $n$ and $m$. In particular, we have proved \begin{equation*} R(\mathbb{K}_{2,n}, W_{m})=3n+4, \end{equation*} whenever $n$ and $m$ are sufficiently large integers satisfying $n\ge 4m$ and $m$ is an odd integer. This proves the $W_m$-goodness of ${\mathbb{K}}_{2,n}$. Our proof combines probabilistic methods with an analysis of structural dependencies. As part of the argument, we resolve a structural rigidity question concerning highly dependent neighbourhoods (Lemma 3.12).

Ramsey Numbers, Ramsey Goodness, Wheel, 2-connectedness