On the 2-coloring diagonal vertex Folkman numbers with minimal possible clique number

ЗаглавиеOn the 2-coloring diagonal vertex Folkman numbers with minimal possible clique number
Вид публикацияJournal Article
Година на публикуване2008
АвториKolev N, Nenov N
СписаниеAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Том98
ключови думиFolkman graphs, Folkman numbers
Резюме

For a graph $G$ the symbol $G\xrightarrow{v}(p,p)$ means that in every 2-coloring of the vertices of $G$, there exists a monochromatic $p$-qlique. The vertex diagonal Folkman numbers $$ F_v(p,p;p+1)=\min\{|V(G)| : G\xrightarrow{v}(p,p) \;\mbox{and}\; K_{p+1}\not\subset G \} $$ are considered. We prove that $F_v(p,p;p+1)\leq\frac{13}{12}p!,\,\;p\geq 4$.

2000 MSC

05C55

Прикачен файлРазмер
PDF icon 98-101-126.pdf1.79 MB