THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC TRIANGLE

Let F(n, k) denote the maximum number of two edge colorings of a graph on n vertices that admit no monochromatic K-k, (a complete graph on k vertices). The following results are proved: F(n, 3) = 2([n2/4]) for all n greater than or equal to 6. F(n, k) = 2(((k-2)/(2k-2)+o(1))n2). In particular, the first result solves a conjecture of Erdos and Roths child. (C) 1996 John Wiley & Sons, Inc.