Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth

Abstract

A graph $\mathcal{H}=(W,E_{\mathcal{H}})$ is said to have {\em bandwidth} at most $b$ if there exists a labeling of $W$ as $w_1,w_2,\dots ,w_n$ such that $|i-j|\le b$ for every edge $w_i{w}_j\in E_{\mathcal{H}}$. We say that $\mathcal{H}$ is a {\em balanced $(\beta ,\Delta )$-graph} if it is a bipartite graph with bandwidth at most $\beta |W|$ and maximum degree at most $\Delta$, and it also has a proper 2-coloring $\chi :W\to [2]$ such that $||{\chi }^{-1}(1)|-|{\chi }^{-1}(2)||\le \beta |{\chi }^{-1}(2)|$. In this paper, we prove that for every $\gamma >0$ and every natural number $\Delta$, there exists a constant $\beta >0$ such that for every balanced $(\beta ,\Delta )$-graph $\mathcal{H}$ on $n$ vertices we have $$R(\mathcal{H},\mathcal{H},C_n)\le (3+\gamma )n$$ for all sufficiently large odd $n$. The upper bound is sharp for several classes of graphs. Let ${\theta }_{n,t}$ be the graph consisting of $t$ internally disjoint paths of length $n$ all sharing the same endpoints. As a corollary, for each fixed $t\ge 1$, $R({\theta }_{n,t},{\theta }_{n,t},C_{nt+\lambda })=(3t+o(1))n,$ where $\lambda =0$ if $nt$ is odd and $\lambda =1$ if $nt$ is even. In particular, we have $R(C_{2n},C_{2n},C_{2n+1})=(6+o(1))n$, which is a special case of a result of Figaj and Łuczak (2018).

17 pages