Coupon Coloring of Snark Graphs - Remadevi, Mithra; Pandurangan, Ragukumar (Journal of the Indonesian Mathematical Society, 2026)
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 $χ_{c}(G)$. Every d-regular graph G has $χ_{c}(G) ≥ (1 - o(1))d/ \log d$ as $d → ∞$, and the proportion of d-regular graphs G for which $χ_{c}(G) ≤ (1 + o(1))d/ \log d$ tends to 1 as $|V(G)| → ∞$. Coupon coloring is known to be NP-complete for k-regular graphs, even when k ≥ 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.