On generalized Ramsey theory:: The bipartite case

Given graphs G and H, a coloring of E(G) is called an (H,q)- coloring if the edges of every copy of H subset of or equal to G together receive at least q colors. Let r(G, H, q) denote the minimum number of colors ina n (H, q)-coloring of G. We determine, for fixed p, the smallest q for which r(K-n,K-n, K-p,K-p, q) is linear in n, the smallest q for which it is quadratic in n. We also determine the smallest q for which r(K-n,K-n, K-p,K-p, q) = n(2) - O(n), and the smallest q for which r(K-n,K-n, K-p,K-p, q) = n(2) - O(1). Our results include showing that r(K-n,K-n, K-2,K-t+1, 2) and r(K-n, K-2,(t+1), 2) are both (1 +o(1)) root n/t as n --> infinity, thereby proving a special case of a conjecture of Chung and Graham. Finally, we determine the exact value of r(K-n,K-n, K-3,K-3, 8), and prove that 2n/3 less than or equal to r(K-n,K-n, C-4, 3) less than or equal to n + 1. Several problems remain open. (C) 2000 Academic Press.