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,\dots,w_n$ such that $|i-j|\leq b$ for every edge $w_iw_j\in E_H$, and a bipartite balanced $(\beta,\Delta)$-graph $H$ is a bipartite graph with bandwidth at most $\beta |W|$ and maximum degree at most $\Delta$, and furthermore it has a proper 2-coloring $\chi :W\rightarrow[2]$ such that $||\chi^{-1}(1)|-|\chi^{-1}(2)||\leq\beta|\chi^{-1}(2)|$. We prove that for any fixed $0<\gamma<1$ and integer $\Delta\ge1$, there exist a constant $\beta=\beta(\gamma,\Delta)>0$ and a natural number $n_0$ such that for every balanced $(\beta,\Delta)$-graph $H$ on $n\geq n_0$ vertices the bipartite Ramsey number $br(H,H)$ is at most $(1+\gamma)n$. In particular, $br(C_{2n},C_{2n})=(2+o(1))n$.
@article{10_37236_7334,
author = {Lili Shen and Qizhong Lin and Qinghai Liu},
title = {Bipartite {Ramsey} numbers for graphs of small bandwidth},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/7334},
zbl = {1391.05181},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7334/}
}
TY - JOUR
AU - Lili Shen
AU - Qizhong Lin
AU - Qinghai Liu
TI - Bipartite Ramsey numbers for graphs of small bandwidth
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/7334/
DO - 10.37236/7334
ID - 10_37236_7334
ER -
%0 Journal Article
%A Lili Shen
%A Qizhong Lin
%A Qinghai Liu
%T Bipartite Ramsey numbers for graphs of small bandwidth
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7334/
%R 10.37236/7334
%F 10_37236_7334
Lili Shen; Qizhong Lin; Qinghai Liu. Bipartite Ramsey numbers for graphs of small bandwidth. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7334
