Discrete Mathematics, Vol. 223 (1-3) (2000) pp. 83-92
© 2000 Elsevier Science B.V. All rights reserved.
PII: S0012-365X(00)00041-8

K2,2-K1,n and K2,n-K2,n bipartite Ramsey numbers

W.A. Carnielli a * carniell@cle.unicamp.br and E.L. Monte Carmelo b carmelo@gauss.dma.uem.br

a Department of Philosophy and Centre for Logic and Epistemology, State University of Campinas, C.P. 6133, Campinas, SP, Brazil
b Department of Mathematics, State University of Maringá, Maringá, PR, Brazil

Received 4 February 1999; received in revised form 15 November 1999; accepted 13 December 1999

Abstract

Some bounds for G1-G2 bipartite Ramsey numbers b(G1;G2) are given, which imply that b(K2,2;K1,n)=n+q for the range q2-q+1<=n<=q2, where q is a prime power. Our new construction establishes in particular that b(K2,n;K2,n)=4n-3 if 4n-3 is a prime power, reinforcing a weaker form of a conjecture due to Beineke and Schwenk. Particular relationships between b(G1;G2) and G1-G2 Ramsey numbers are also determined.

MSC: 05C55

Keywords: Generalized Ramsey theory; Bipartite Ramsey number; Strongly regular graphs

*Corresponding author

[Full text] (PDF 98 Kb)


Mirror sites: www.europe | www.usa | www.japan

© Copyright 2000, Elsevier Science, All rights reserved.