Multiple vertex coverings by cliques

For positive integers m 1 ,…, m k , let f ( m 1 ,…, m k ) be the minimum order of a graph whose edges can be colored with k colors such that every vertex is in a clique of cardinality m i , all of whose edges have the i th color for all i  = 1,2,…, k . The value for k  = 2 was determined by Entringer et al. ( J Graph Theory 24 (1997), 21–23). We show that if k is fixed then f ( m ,…, m ) = 2 km – o ( m ). We also provide some exact values for f ( m , n , 2). © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 157–167, 2005