| 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 |