Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Google Scholar, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Induced ramsey numbers

Texto completo
Autor(es):
Kohayakawa‚ Y. ; Prömel‚ H.J. ; Rödl‚ V.
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: COMBINATORICA; v. 18, n. 3, p. 373-404, 1998.
Resumo

We investigate the induced Ramsey number r(ind)(G,H) of pairs of graphs (G,H). This number is defined to be the smallest possible order of a graph Gamma with the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with k = \V(G)\less than or equal to t=\V(H)\, we have r(ind)(G, H)less than or equal to t(Ck log q), where q = chi(H) is the chromatic number of H and C is some universal constant. Furthermore, we also investigate r(ind)(G,H) imposing some conditions on G. For instance, we prove abound that is polynomial in both k and t in the case in which G is a tree. Our methods of proof employ certain random graphs based on projective planes. (AU)

Processo FAPESP: 96/04505-2 - Aspectos estruturais e algorítmicos de objetos combinatórios
Beneficiário:Yoshiharu Kohayakawa
Modalidade de apoio: Auxílio à Pesquisa - Temático