Coupon Coloring of Snark Graphs

A k-coupon coloring of a graph $G$ is a k-coloring of G by colors [k] = {1, 2, . . ., k} such that the neighborhood of every vertex of G contains vertices of all colors from [k]. The maximum integer k for which a k-coupon coloring exists is called the coupon coloring number of G, and it is denoted by $\chi_{c}(G)$. Every d-regular graph G has $\chi_{c}(G) \geq (1 - o(1))d/ \log d$ as $d \rightarrow \infty$, and the proportion of d-regular graphs G for which $\chi_{c}(G) \leq (1 + o(1))d/ \log d$ tends to 1 as $|V(G)| \rightarrow \infty$. Coupon coloring is known to be NP-complete for k-regular graphs, even when k \geq 3. Snarks form a subclass of cubic graphs that are non-Hamiltonian. This motivated us to focus on investigating coupon coloring specifically in the context of snark graphs.