Local Rainbow Colorings for Various Graphs

Motivated by a problem in theoretical computer science suggested by Wigderson, Alon and Ben-Eliezer studied the following extremal problem systematically one decade ago. Given a graph H, let C (n, H) be the minimum number k such that the following holds. There are n colorings of E (K₍) with k colors, each associated with one of the vertices of K₍, such that for every copy T of H in K₍, at least one of the colorings that are associated with V (T) assigns distinct colors to all the edges of E (T). In this paper, we obtain several new results in this problem including: For paths of short length, we show that C (n, P₄) = (n^1/5) and C (n, Pₓ) = (n^1/3) with t\5, 6\, which significantly improve the previously known lower bounds (n) ^ (1). We make progress on the problem of Alon and Ben-Eliezer about complete graphs, more precisely, we show that C (n, Kₑ) = (n^2/3) when r 8, and C (n, Kₒ, ₓ) = (n^2/3) for all t s 7. When H is a star with at least 4 leaves, a matching of size at least 4, or a path of length at least 7, we give a new lower bound for C (n, H). We also show that for any graph H with at least 6 edges, C (n, H) is polynomial in n. All of these improve the corresponding results obtained by Alon and Ben-Eliezer.