ON THE VERTEX FOLKMAN NUMBERS $F_v(\underbrace{2,...,2}_R;R-1)$ and $F_v(\underbrace{2,...,2}_R;R-2)$

TitleON THE VERTEX FOLKMAN NUMBERS $F_v(\underbrace{2,...,2}_R;R-1)$ and $F_v(\underbrace{2,...,2}_R;R-2)$
Publication TypeJournal Article
Year of Publication2013
AuthorsNenov N
JournalAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Volume101
KeywordsFolkman graphs, Folkman numbers
Abstract

For a graph $G$ the symbol $G\overset{v}{\rightarrow}(a_1,...,a_r)$ means that in every $r$-coloring of the vertices of $G$ for some $i\in\{1,2,...,r\}$ there exists a monochromatic $a_i$-clique of color $i$. The vertex Folkman numbers \[F_v(\underbrace{a_1,...,a_r}_r;q) =\min\{|V(G)|:G\overset{v}{\rightarrow}(a_1,...,a_r)\text{ and }K_q\nsubseteq G\}\] are considered. We prove that \[F_v(\underbrace{2,...,2}_r;r-1) = r + 7, r \geq 6\text{ and } F_v(\underbrace{2,...,2}_r;r-2) = r + 9, r \geq 8.\]

2000 MSC

05C55

AttachmentSize
PDF icon 101-005-017.pdf157.88 KB