On the vertex Folkman numbers $F_v(a_1, ..., a_s; m - 1)$ when $\max\{a_1, ..., a_s\} = 6$ or $7$
| Autor: | Bikov, Aleksandar, Nenov, Nedyalko |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Journal of Combinatorial Mathematics and Combinatorial Computing, 109:213-243, 2019 |
| Druh dokumentu: | Working Paper |
| Popis: | Let $G$ be a graph and $a_1, ..., a_s$ be positive integers. Then $G \overset{v}{\rightarrow} (a_1, ..., a_s)$ means that for every coloring of the vertices of $G$ in $s$ colors there exists $i \in \{1, ..., s\}$, such that there is a monochromatic $a_i$-clique of color $i$. The vertex Folkman number $F_v(a_1, ..., a_s; q)$ is defined by the equality: $$ F_v(a_1, ..., a_s; q) = \min\{|V(G)| : G \overset{v}{\rightarrow} (a_1, ..., a_s) \mbox{ and } K_q \not\subseteq G\}. $$ Let $m = \sum\limits_{i=1}^s (a_i - 1) + 1$. It is easy to see that $F_v(a_1, ..., a_s; q) = m$ if $q \geq m + 1$. In [11] it is proved that $F_v(a_1, ..., a_s; m) = m + \max\{a_1, ..., a_s\}$. We know all the numbers $F_v(a_1, ..., a_s; m - 1)$ when $\max\{a_1, ..., a_s\} \leq 5$ and none of these numbers is known if $\max\{a_1, ..., a_s\} \geq 6$. In this paper we compute the numbers $F_v(a_1, ..., a_s; m - 1)$ when $\max\{a_1, ..., a_s\} = 6$. Comment: In the current version we use new faster algorithms with the help of which we reproduce the results from the previous version and we also prove new theorems (Theorem 1.5, Theorem 1.6, Theorem 1.7, Theorem 1.8) |
| Databáze: | arXiv |
| Externí odkaz: |
|