New Upper Bound for the Edge Folkman Number Fe(3,5;13)

2000 Mathematics Subject Classification: 05C55.

For a given graph G let V(G) and E(G) denote the vertex and the edge set of G respevtively. The symbol G e → (a1, …, ar) means that in every r-coloring of E(G) there exists a monochromatic ai-clique of color i for some i ∈ {1,…,r}. The edge Folkman numbers are defined by the equality Fe(a1, …, ar; q) = min{|V(G)| : G e → (a1, …, ar; q) and cl(G) < q}. In this paper we prove a new upper bound on the edge Folkman number Fe(3,5;13), namely Fe(3,5;13) ≤ 21. This improves the bound Fe(3,5;13) ≤ 24, proved by Kolev and Nenov.

Supported by the Scientific Research Fund of the St. Kl. Ohridski Sofia University under contract 90-2008.