On the independence number of $(3,3)$-Ramsey graphs and the Folkman number $F_e(3,3;4)$

Abstract

The graph $G$ is called a $(3,3)$-Ramsey graph if in every coloring of the edges of $G$ in two colors there is a monochromatic triangle. The minimum number of vertices of the $(3,3)$-Ramsey graphs without 4-cliques is denoted by $F_e(3,3;4)$. The number $F_e(3,3;4)$ is referred to as the most wanted Folkman number. It is known that $20\le F_e(3,3;4)\le 786$. In this paper we prove that if $G$ is an $n$-vertex $(3,3)$-Ramsey graph without 4-cliques, then $\alpha (G)\le n-16$, where $\alpha (G)$ denotes the independence number of $G$. Using the newly obtained bound on $\alpha (G)$ and complex computer calculations we obtain the new lower bound $$F_e(3,3;4)\ge 21.$$

The new results are the same as in the previous version. Some improvements are made and several tables are added

References in corpus (4)

• Use of MAX-CUT for Ramsey Arrowing of Triangles
• The edge Folkman number $F_e(3,3;4)$ is greater than 19
• Small minimal $(3,3)$-Ramsey graphs
• Computation and Bounding of Folkman Numbers