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

preprint2022arXivOpen access

Abstract

A graph H=(W,EH)\mathcal{H}=(W,E_\mathcal{H}) is said to have {\em bandwidth} at most bb if there exists a labeling of WW as w1,w2,…,wnw_1,w_2,\dots,w_n such that ∣i−j∣≤b|i-j|\leq b for every edge wiwj∈EHw_iw_j\in E_\mathcal{H}. We say that H\mathcal{H} is a {\em balanced (β,Δ)(β,Δ)-graph} if it is a bipartite graph with bandwidth at most β∣W∣β|W| and maximum degree at most ΔΔ, and it also has a proper 2-coloring χ:W→[2]χ:W\rightarrow[2] such that ∣∣χ−1(1)∣−∣χ−1(2)∣∣≤β∣χ−1(2)∣||χ^{-1}(1)|-|χ^{-1}(2)||\leqβ|χ^{-1}(2)|. In this paper, we prove that for every γ>0γ>0 and every natural number ΔΔ, there exists a constant β>0β>0 such that for every balanced (β,Δ)(β,Δ)-graph H\mathcal{H} on nn vertices we have R(H,H,Cn)≤(3+γ)nR(\mathcal{H}, \mathcal{H}, C_n) \leq (3+γ)n for all sufficiently large odd nn. The upper bound is sharp for several classes of graphs. Let θn,tθ_{n,t} be the graph consisting of tt internally disjoint paths of length nn all sharing the same endpoints. As a corollary, for each fixed t≥1t\geq 1, R(θn,t,θn,t,Cnt+λ)=(3t+o(1))n,R(θ_{n, t},θ_{n, t}, C_{nt+λ})=(3t+o(1))n, where λ=0λ=0 if ntnt is odd and λ=1λ=1 if ntnt is even. In particular, we have R(C2n,C2n,C2n+1)=(6+o(1))nR(C_{2n},C_{2n}, C_{2n+1})=(6+o(1))n, which is a special case of a result of Figaj and Łuczak (2018).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.