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

preprint2019arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.