New Upper Bound for a Class of Vertex Folkman Numbers
New Upper Bound for a Class of Vertex Folkman Numbers
复制标题
一类顶点 Folkman 数的新上限
DOI：
10.37236/1040
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
N. Nenov
中科院分区：
文献类型：
--
作者：
N. Kolev;N. Nenov
设$a_1, \ldots, a_r$为正整数$m=\sum_{i=1}^{r} (a_{i}-1)+1$和$p= \max \{a_1, \ldots, a_r\}$。对于图形$G$，符号$G\rightarrow \{a_1, \ldots, a_r\}$表示在$G$顶点的每个$r$ -着色中，存在一个单色的$a_i$ -彩色团$i$对于某些$i=1, \ldots, r$。考虑了顶点Folkman数$F(a_1,\dots,a_r;m-1)=\min \{| V(G) | : G\rightarrow (a_1 \ldots a_r)$和$K_{m-1} \not \subseteq G \}$。我们证明了$F(a_1, \ldots, a_r; m-1) \leq m+3p$$p \geq 3$。这个不等式改进了Łuczak， Rucinski和Urbanski（2001）得到的这些数的界。
Let $a_1, \ldots, a_r$ be positive integers, $m=\sum_{i=1}^{r} (a_{i}-1)+1$ and $p= \max \{a_1, \ldots, a_r\}$. For a graph $G$ the symbol $G\rightarrow \{a_1, \ldots, a_r\}$ denotes that in every $r$-coloring of the vertices of $G$ there exists a monochromatic $a_i$-clique of color $i$ for some $i=1, \ldots, r$. The vertex Folkman numbers $F(a_1,\dots,a_r;m-1)=\min \{| V(G) | : G\rightarrow (a_1 \ldots a_r)$ and $K_{m-1} \not \subseteq G \}$ are considered. We prove that $F(a_1, \ldots, a_r; m-1) \leq m+3p$, $p \geq 3$. This inequality improves the bound for these numbers obtained by Łuczak, Rucinski and Urbanski (2001).