On restricted edge-colorings of bicliques (Q1850030)

For graphs \(G\) and \(H\) and integers \(q \leq q'\), an \((H; q, q')\)-coloring of \(G\) is an edge coloring of \(G\) such that every copy of \(H\) in \(G\) receives at least \(q\) colors and at most \(q'\) colors. The maximum number and minimum number of colors in an \((H; q, q')\)-coloring of \(G\) is denoted by \(r(G, H: q, q')\) and \(R(G, H: q, q')\) respectively. The numbers \(r\) and \(R\) are investigated for complete bipartite graphs \(G\) and \(H\). For example, it is shown that \(R(K_{n,n}, K_{p,p}: q, p) = n\) for \(2 \leq p \leq n\) and \(1 \leq q \leq p\). Results on the numbers \(r\) and \(R\) are used to improve bounds on bipartite Turán numbers.