Ramsey numbers for bipartite graphs with small bandwidth |
| |
| Institution: | 1. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil;2. Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA;3. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, P.O. Box 127, Budapest, H-1364, Hungary;4. Fachbereich Mathematik, Universität Hamburg, Bundesstraße 55, D-20146 Hamburg, Germany;5. Technische Universität Hamburg-Harburg, Institut für Mathematik, Schwarzenbergstraße 95, 21073 Hamburg, Germany |
| |
| Abstract: | We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
