Name
Abstract | ||
|---|---|---|
In 1970, J. Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every r coloring of vertices of H yields at least one monochromatic copy of G. His proof gives no good bound on the order of graph H, i.e. the order of H is bounded by an iterated power function. A related problem was studied by Łuczak, Rucinski and Urbanski, who gave some explicite bound on the order of H when G is a clique. In this note we give an alternative proof of Folkman's theorem with the relatively small order of H bounded from above by O(n3 log3 n). This improves Łuczak, Rucinski and Urbanski's result. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78773-0_41 | LATIN |
Keywords | Field | DocType |
order n,small order,clique number,vertex folkman number,integer r,j. folkman,graph g,h yield,graph h,n3 log3 n,alternative proof,ramsey theory,upper bound | Integer,Ramsey theory,Discrete mathematics,Combinatorics,Bound graph,Clique,Vertex (geometry),Upper and lower bounds,Semi-symmetric graph,Mathematics,Bounded function | Conference |
Volume | ISSN | ISBN |
4957 | 0302-9743 | 3-540-78772-0 |
Citations | PageRank | References |
2 | 0.53 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Vojtěch Rödl | 2 | 887 | 142.68 |