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.