Modified vertex Folkman numbers

Abstract

Let $a_1,...,a_s$ be positive integers. For a graph $G$ the expression $$G\stackrel{v}{\to }(a_1,...,a_s)$$ means that for every coloring of the vertices of $G$ in $s$ colors ($s$-coloring) there exists $i\in \{1,...,s\}$, such that there is a monochromatic $a_i$-clique of color $i$. If $m$ and $p$ are positive integers, then $$G\stackrel{v}{\to }m{|}_p$$ means that for arbitrary positive integers $a_1,...,a_s$ ($s$ is not fixed), such that ${\sum }_{i=1}^s(a_i-1)+1=m$ an $\max \{a_1,...,a_s\}\le p$ we have $G\stackrel{v}{\to }(a_1,...,a_s)$. Let $$ \widetilde{\mathcal{H}}({m}\big\vert_{p}; q) = \{G : G \overset{v}{\rightarrow} {m}\big\vert_{p} \mbox{ and } ω(G) < q\}. $$ The modified vertex Folkman numbers are defined by the equality $$\tilde{F}(m{|}_p;q)=\min \{|V(G)|:G\in \tilde{\mathcal{H}}(m{|}_p;q)\}.$$ If $q\ge m$ these numbers are known and they are easy to compute. In the case $q=m-1$ we know all of the numbers when $p\le 5$. In this work we consider the next unknown case $p=6$ and we prove with the help of a computer that $$\tilde{F}(m{|}_6;m-1)=m+10.$$

References in corpus (1)

• The vertex Folkman numbers $F_v(a_1,...,a_s;m-1)=m+9$, if $\max \{a_1,...,a_s\}=5$

Cited by in corpus (2)

• Computation and Bounding of Folkman Numbers
• Lower bounding the Folkman numbers $F_v(a_1,...,a_s;m-1)$