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 © 2012 Wiley Periodicals, Inc. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1002/rsa.20397 | Random Struct. Algorithms |
Keywords | Field | DocType |
monochromatic copy,wiley periodicals,clique number,graph g,graph h,induced folkman number,inc. random struct,smallest graph h | Discrete mathematics,Graph,Monochromatic color,Clique number,Combinatorics,Bound graph,Vertex (geometry),Upper and lower bounds,struct,Mathematics | Journal |
Volume | Issue | ISSN |
40 | 4 | 1042-9832 |
Citations | PageRank | References |
1 | 0.39 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrzej Dudek | 1 | 114 | 23.10 |
Reshma Ramadurai | 2 | 17 | 3.32 |
Vojtěch Rödl | 3 | 887 | 142.68 |