Induced ramsey numbers

Autor(es)

Kohayakawa‚ Y. ; Prömel‚ H.J. ; Rödl‚ V.

• 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