EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Coupon Coloring of Snark Graphs

Mithra Remadevi, Ragukumar Pandurangan

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →