科研之友
微信
新浪微博
Facebook
分享链接
摘要
The vertex Folkman number F (r, n, m), n < m, is the smallest integer t such that there exists a K(m)-free graph of order t with the property that every r-coloring of its vertices yields a monochromatic copy of K(n). The problem of bounding the Folkman numbers has been studied by several authors. However, in the most restrictive case, when m = n + 1, no polynomial bound has been known for such numbers. In this paper we show that the vertex Folkman numbers F(r, n, n + 1) are bounded from above by O(n(2) log(4) n). Furthermore, for any fixed r and any small epsilon > 0 we derive the linear upper bound when the cliques bigger than (2 + epsilon)n are forbidden.
- 出版日期2010-3
