
doi: 10.37236/7334
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$.
Graph labelling (graceful graphs, bandwidth, etc.), bipartite Ramsey number, regularity lemma, balanced \((\beta,\Delta)\)-graph, Generalized Ramsey theory
Graph labelling (graceful graphs, bandwidth, etc.), bipartite Ramsey number, regularity lemma, balanced \((\beta,\Delta)\)-graph, Generalized Ramsey theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
