Induced ramsey numbers

Author(s)

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

• Document type: Journal article
• Source: COMBINATORICA; v. 18, n. 3, p. 373-404, 1998.

Abstract

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)

• FAPESP's process: 96/04505-2 - Structural and algorithmic aspects of combinatorial objects
• Grantee: Yoshiharu Kohayakawa
• Support Opportunities: Research Projects - Thematic Grants