Coupon Coloring of Snark Graphs
Journal of the Indonesian Mathematical Society · 01.05.2026 · 32 (2) · 2069
DOI: 10.22342/jims.v32i2.2069 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the Indonesian Mathematical Society, online erschienen am 01.05.2026. Verfasst von Mithra Remadevi und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Remadevi, M., & Pandurangan, R. (2026). Coupon Coloring of Snark Graphs. Journal of the Indonesian Mathematical Society, 32(2), 2069. https://doi.org/10.22342/jims.v32i2.2069
Vancouver
Remadevi M, Pandurangan R. Coupon Coloring of Snark Graphs. Journal of the Indonesian Mathematical Society. 2026;32(2):2069. doi:10.22342/jims.v32i2.2069
BibTeX
@article{Remadevi2026,
author = {Remadevi, Mithra and Pandurangan, Ragukumar},
title = {Coupon Coloring of Snark Graphs},
journal = {Journal of the Indonesian Mathematical Society},
year = {2026},
volume = {32},
number = {2},
pages = {2069},
doi = {10.22342/jims.v32i2.2069}
}
EUVIMED