Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: On the Ramsey problem for multicolor bipartite graphs
Author: Carnielli, WA
Carmelo, ELM
Abstract: Given i,j positive integers, let K-i,K-j denote a bipartite complete graph and let R-r(m, n) be the smallest integer a such that for any r-coloring of the edges of K-a,K-a one can always find a monochromatic subgraph isomorphic to K-m,K-n. In other words, if a greater than or equal to R-r(m, n) then every matrix a x a with entries in {0, 1,..., r - 1} always contains a submatrix m x n or n x m whose entries are i, 0 less than or equal to i less than or equal to r - 1. We shall prove that R-2(m, n) less than or equal to 2(m)(n - 1) + 2(m-1) - 1, Which generalizes the previous results R-2(2, n) less than or equal to 4n - 3 and R-2(3, n) less than or equal to 8n - 5 due to Beineke and Schwenk. Moreover, we find a class of lower bounds based on properties of orthogonal Latin squares which establishes that lim(r --> infinity) R-r(2, 2)r(-2) = 1. (C) 1999 Academic Press.
Country: EUA
Editor: Academic Press Inc
Citation: Advances In Applied Mathematics. Academic Press Inc, v. 22, n. 1, n. 48, n. 59, 1999.
Rights: fechado
Identifier DOI: 10.1006/aama.1998.0620
Date Issue: 1999
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000077703900004.pdf84.92 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.