Three-Color Ramsey Number of an Odd Cycle Versus Bipartite Graphs with Small Bandwidth

A graph H = (W, E-H) is said to have bandwidth at most b if there exists a labeling of W as w(1), w(2),..., w(n) such that vertical bar i - j vertical bar <= b for every edge w(i)w(j) is an element of E-H. We say that H is a balanced (beta, Delta)-graph if it is a bipartite graph with bandwidth at most beta vertical bar W vertical bar and maximum degree at most Delta, and it also has a proper 2-coloring chi : W -> [2] such that parallel to chi(-1)(1)vertical bar - vertical bar chi(-1)(2)parallel to <= beta vertical bar 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 H on n vertices we have R(H, H, C-n) <= (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 >= 1, R(theta(n,t), theta(n,t), Cnt+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, C2n+1) = (6 + o(1))n, which is a special case of a result of Figaj and Luczak (2018).