On Coupon Colorings of Graphs

Abstract

Let $G$ be a graph with no isolated vertices. A {\em $k$-coupon coloring} of $G$ is an assignment of colors from $[k]:=\{1,2,\dots ,k\}$ to the vertices of $G$ such that the neighborhood of every vertex of $G$ contains vertices of all colors from $[k]$. The maximum $k$ for which a $k$-coupon coloring exists is called the {\em coupon coloring number} of $G$, and is denoted ${\chi }_c(G)$. In this paper, we prove that every $d$-regular graph $G$ has ${\chi }_c(G)\ge (1-o(1))d/\log d$ as $d\to \infty$, and the proportion of $d$-regular graphs $G$ for which ${\chi }_c(G)\le (1+o(1))d/\log d$ tends to $1$ as $|V(G)|\to \infty$.