New Upper Bound for a Class of Vertex Folkman Numbers

  • N. Kolev
  • N. Nenov

Abstract

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, Ruciński and Urbański (2001).

Published
2006-02-15
Article Number
R14