An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.