Coupon Coloring of Snark Graphs - Remadevi, Mithra; Pandurangan, Ragukumar (IndoMS, 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/ d as d → ∞, and the proportion of d-regular graphs G for which χ_c(G) ≤ (1 + o(1))d/ 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.