Split and balanced colorings of complete graphs

An (r,n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K-n in color i. This generalizes the notion of split graphs which correspond to (2,2)-split colorings. The smallest N for which the complete graph K-N has a coloring which is not (r,n)-split is denoted by f(r)(n). Balanced (r,n)-colorings are defined as edge r-colorings of K-N such that every subset of inverted right perpendicular N/r inverted left perpendicular vertices contains a monochromatic K-n in all colors. Then g(r)(n) is defined as the smallest N such that K-N has a balanced (r,n)-coloring. The definitions imply that f(r)(n)less than or equal to g(r)(n). The paper gives estimates and exact values of these functions for various choices of parameters. (C) 1999 Elsevier Science B.V. All rights reserved.