An almost quadratic bound on vertex Folkman numbers
An almost quadratic bound on vertex Folkman numbers
复制标题
顶点 Folkman 数的近似二次界
DOI：
10.1016/j.jctb.2009.05.004
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
V. Rödl
中科院分区：
文献类型：
--
作者：
A. Dudek;V. Rödl
顶点Folkman数F（r，n，m），n<m，是最小的整数t，使得存在一个t阶无Km图，其性质是它的顶点的每一个r-着色都产生Kn的单色副本。Folkman数的边界问题已经被几位作者研究过。然而，在最严格的情况下，当m=n+1时，对于这样的数没有多项式界限。本文证明了顶点Folkman数F（r，n，n+1）的上有界性为O（n2 log 4 n）.此外，对于任意固定的r和任意小的ε>0，当禁止大于（2+ε）n的团时，我们得到了线性上界.
The vertex Folkman number F(r,n,m), n<m, is the smallest integer t such that there exists a Km-free graph of order t with the property that every r-coloring of its vertices yields a monochromatic copy of Kn. 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(n2log4n). Furthermore, for any fixed r and any small ε>0 we derive the linear upper bound when the cliques bigger than (2+ε)n are forbidden.