Maximal antiramsey graphs and the strong chromatic number

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of X_s(n, e, L), defined to be the minimum number of colors needed to edge-color some graph G(n, ?) with n vertices and e edges so that all copies of L in it are totally multicolored. It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well-studied (but little understood) functions r_k(n), defined to be the size of the largest subset of {1, 2,…, n} containing no k-term arithmetic progression, and g(n; k, l), defined to be the maximum number of triples which can be formed from {1, 2,…, n} so that no two triples share a common pair, and no k elements of {1, 2,…, n} span l triples.