On coupon colorings of graphs

Let GG be a graph with no isolated vertices. A kk-coupon coloring   of GG is an assignment of colors from [k]≔{1,2,…,k}[k]≔{1,2,…,k} to the vertices of GG such that the neighborhood of every vertex of GG contains vertices of all colors from [k][k]. The maximum kk for which a kk-coupon coloring exists is called the coupon coloring number   of GG, and is denoted χc(G)χc(G). In this paper, we prove that every dd-regular graph GG has χc(G)≥(1−o(1))d/logdχc(G)≥(1−o(1))d/logd as d→∞d→∞, and the proportion of dd-regular graphs GG for which χc(G)≤(1+o(1))d/logdχc(G)≤(1+o(1))d/logd tends to 1 as |V(G)|→∞|V(G)|→∞.An injective  kk-coloring   of a graph GG is an assignment of colors from [k][k] to the vertices of GG such that no two vertices joined by a path of length two in GG have the same color. The minimum kk for which such a coloring exists is called the injective coloring number   of GG, denoted χi(G)χi(G). In this paper, we also discuss injective colorings of Hamming graphs.