Multicolour bipartite ramsey number of paths

Matija Bucić; Shoham Letzter

doi:10.37236/8458

Multicolour bipartite ramsey number of paths

Matija Bucić, Shoham Letzter

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

The k-colour bipartite Ramsey number of a bipartite graph H is the least integer N for which every k-edge-coloured complete bipartite graph K_N,N contains a monochromatic copy of H. The study of bipartite Ramsey numbers was initiated over 40 years ago by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-colour bipartite Ramsey number of paths. Recently the 3- colour Ramsey number of paths and (even) cycles, was essentially determined as well. Improving the results of DeBiasio, Gyárfás, Krueger, Ruszinkó, and Sárközy, in this paper we determine asymptotically the 4-colour bipartite Ramsey number of paths and cycles. We also provide new upper bounds on the k-colour bipartite Ramsey numbers of paths and cycles which are close to being tight.

Original language	English (US)
Article number	P3.60
Journal	Electronic Journal of Combinatorics
Volume	26
Issue number	3
DOIs	https://doi.org/10.37236/8458
State	Published - 2019
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/8458

Cite this

@article{2a306a28d30248c882127f95e8c81d3c,

title = "Multicolour bipartite ramsey number of paths",

abstract = "The k-colour bipartite Ramsey number of a bipartite graph H is the least integer N for which every k-edge-coloured complete bipartite graph KN,N contains a monochromatic copy of H. The study of bipartite Ramsey numbers was initiated over 40 years ago by Faudree and Schelp and, independently, by Gy{\'a}rf{\'a}s and Lehel, who determined the 2-colour bipartite Ramsey number of paths. Recently the 3- colour Ramsey number of paths and (even) cycles, was essentially determined as well. Improving the results of DeBiasio, Gy{\'a}rf{\'a}s, Krueger, Ruszink{\'o}, and S{\'a}rk{\"o}zy, in this paper we determine asymptotically the 4-colour bipartite Ramsey number of paths and cycles. We also provide new upper bounds on the k-colour bipartite Ramsey numbers of paths and cycles which are close to being tight.",

author = "Matija Buci{\'c} and Shoham Letzter",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2019",

doi = "10.37236/8458",

language = "English (US)",

volume = "26",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "3",

}

TY - JOUR

T1 - Multicolour bipartite ramsey number of paths

AU - Bucić, Matija

AU - Letzter, Shoham

N1 - Publisher Copyright: © The authors.

PY - 2019

Y1 - 2019

N2 - The k-colour bipartite Ramsey number of a bipartite graph H is the least integer N for which every k-edge-coloured complete bipartite graph KN,N contains a monochromatic copy of H. The study of bipartite Ramsey numbers was initiated over 40 years ago by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-colour bipartite Ramsey number of paths. Recently the 3- colour Ramsey number of paths and (even) cycles, was essentially determined as well. Improving the results of DeBiasio, Gyárfás, Krueger, Ruszinkó, and Sárközy, in this paper we determine asymptotically the 4-colour bipartite Ramsey number of paths and cycles. We also provide new upper bounds on the k-colour bipartite Ramsey numbers of paths and cycles which are close to being tight.

AB - The k-colour bipartite Ramsey number of a bipartite graph H is the least integer N for which every k-edge-coloured complete bipartite graph KN,N contains a monochromatic copy of H. The study of bipartite Ramsey numbers was initiated over 40 years ago by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-colour bipartite Ramsey number of paths. Recently the 3- colour Ramsey number of paths and (even) cycles, was essentially determined as well. Improving the results of DeBiasio, Gyárfás, Krueger, Ruszinkó, and Sárközy, in this paper we determine asymptotically the 4-colour bipartite Ramsey number of paths and cycles. We also provide new upper bounds on the k-colour bipartite Ramsey numbers of paths and cycles which are close to being tight.

UR - http://www.scopus.com/inward/record.url?scp=85073589475&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073589475&partnerID=8YFLogxK

U2 - 10.37236/8458

DO - 10.37236/8458

M3 - Article

AN - SCOPUS:85073589475

SN - 1077-8926

VL - 26

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 3

M1 - P3.60

ER -

Multicolour bipartite ramsey number of paths

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this