On induced Folkman numbers |
| |
| Authors: | Andrzej Dudek Reshma Ramadurai Vojtěch Rödl |
| |
| Institution: | 1. Department of Mathematics, Western Michigan University, Kalamazoo, Michigan 49008;2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213;3. Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322 |
| |
| Abstract: | In 1970, Folkman proved that for any graph G there exists a graph H with the same clique number as G. In addition, any r ‐coloring of the vertices of H yields a monochromatic copy of G. For a given graph G and a number of colors r let f(G, r) be the order of the smallest graph H with the above properties. In this paper, we give a relatively small upper bound on f(G, r) as a function of the order of G and its clique number. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 40, 493–500, 2012 |
| |
| Keywords: | Folkman numbers |
|
|
