Coupon Coloring of Snark Graphs

Mithra Remadevi; Ragukumar Pandurangan

doi:10.22342/jims.v32i2.2069

Mithra Remadevi ⁽¹⁾ , Ragukumar Pandurangan ⁽²⁾

(1) Department of Mathematics, Vellore Institute of Technology, India,

(2) Department of Mathematics, Vellore Institute of Technology, India

https://doi.org/10.22342/jims.v32i2.2069

Issue
Vol. 32 No. 2 (2026): JUNE

Submitted
May 22, 2025

Accepted
January 31, 2026

Published
May 1, 2026

Keywords:

coupon coloring number, snark graph, regular graph

XML PDF

Abstract

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.

Full text article

Generated from XML file

References

J. A. Bondy and U. S. R. Murty, “Graph theory with applications,” 1976.

D. B. West, “Introduction to graph theory,” 2001.

B. Chen, J. H. Kim, M. Tait, and J. Verstraete, “On coupon colorings of graphs,” Discrete Applied Mathematics, vol. 193, pp. 94–101, 2015. https://doi.org/10.1016/j.dam.2015.04.026.

Y. Shi, M. Wei, J. Yue, and Y. Zhao, “Coupon coloring of some special graphs,” Journal of Combinatorial Optimization, vol. 33, pp. 156–164, 2017. https://doi.org/10.1007/s10878-015-9942-2.

E. J. Cockayne, R. Dawes, and S. T. Hedetniemi, “Total domination in graphs,” Networks, vol. 10, no. 3, pp. 211–219, 1980. https://doi.org/10.1002/net.3230100304.

H. Chen and Z. Jin, “Coupon coloring of cographs,” Applied Mathematics and Computation, vol. 308, pp. 90–95, 2017. https://doi.org/10.1016/j.amc.2017.03.023.

Z. L. Nagy, “Coupon-coloring and total domination in hamiltonian planar triangulations,” Graphs and Combinatorics, vol. 34, pp. 1385–1394, 2018. https://doi.org/10.1007/s00373-018-1945-1

P. Francis and D. Rajendraprasad, “On coupon coloring of cartesian product of some graphs,” in Algorithms and Discrete Applied Mathematics: 7th International Conference, CALDAM 2021, Rupnagar, India, February 11–13, 2021, Proceedings 7, pp. 309–316, Springer, 2021. https://doi.org/10.1007/978-3-030-67899-9_25.

R. Thankachan and P. Rajamani, “Coupon coloring of lexicographic product of graphs,” The Art of Discrete and Applied Mathematics, vol. 6, no. 1, pp. P1–03, 2023. https://doi.org/10.26493/2590-9770.1507.dc5.

R. Isaacs, “Infinite families of nontrivial trivalent graphs which are not tait colorable,” The American Mathematical Monthly, vol. 82, no. 3, pp. 221–239, 1975. https://doi.org/10.1080/00029890.1975.11993805.

J. J. Watkins, “Snarks,” Annals of the New York Academy of Sciences, vol. 576, no. 1, pp. 606–622, 1989. https://doi.org/10.1111/j.1749-6632.1989.tb16441.x.

C. Campos, S. Dantas, and C. P. de Mello, “The total-chromatic number of some families of snarks,” Discrete Mathematics, vol. 311, no. 12, pp. 984–988, 2011. https://doi.org/10.1016/j.disc.2011.02.013.

A. Cavicchioli, T. Murgolo, B. Ruini, and F. Spaggiari, “Special classes of snarks,” Acta Applicandae Mathematica, vol. 76, pp. 57–88, 2003. https://doi.org/10.1023/A:1022864000162.

D. Sasaki, S. Dantas, and C. M. de Figueiredo, “On coloring problems of snark families,” Electronic Notes in Discrete Mathematics, vol. 37, pp. 45–50, 2011. https://doi.org/10.1016/j.endm.2011.05.009.

J. J. Watkins, “On the construction of snarks,” Ars Combin, vol. 16, pp. 111–124, 1983.

K. K. Galvao, “Developments of fulkerson’s conjecture,” Institute of Computing, University of Campinas, 2013.

R. Isaacs, “Loupekhine’s snarks: a bifamily of non-tait-colorable graphs,” J. Combin. Theory B, 1976. https://doi.org/10.2307/2319844.

G. Szekeres, “Polyhedral decompositions of cubic graphs,” Bulletin of the Australian Mathematical Society, vol. 8, no. 3, pp. 367–387, 1973. https://doi.org/10.1017/S0004972700042660.

Authors

Mithra Remadevi

Department of Mathematics, Vellore Institute of Technology

Ragukumar Pandurangan

Department of Mathematics, Vellore Institute of Technology

ragukumar2003@gmail.com (Primary Contact)

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

Download Citation

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Downloads

Download data is not yet available.

1. INTRODUCTION

In this paper we consider the graphs that are simple, finite and undirected. Let $V ( G )$ and $E ( G )$ be the vertex set and edge set of the graph $G \ = \ ( V , E )$ respectively. The neighbourhood of the vertex $x \in V ( G )$, denoted as ${ \mathcal { N } } ( x )$ is the set of all vertices that are adjacent to $x$. The degree of a vertex $x$ in a graph is the number of vertices adjacent to $x$. The minimum degree of a graph is denoted as $\delta ( G )$. For the standard graph terminology notions, we in general follow [1,2]. Graph coloring is one of the important and fertile area in the field of Graph Theory. Among various coloring problems, Chen et al.[3]introduced coupon coloring in the year 2015. Let $G$ be a graph with no isolated vertices. A $k$-coupon coloring of G is an assignment of colors from $[ k ] = \{ 1 , 2 , \ldots , k \}$ to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from $[ k ]$. The maximum k for which a k-coupon coloring exists is called the coupon coloring number of G, and is denoted by $\chi_c(G)$[3]. The term coupon coloring is motivated by viewing colors as diferent types of coupons, where each vertex is required to obtain from its neighbors coupons of all types. If we imagine users $v _ { 1 } , v _ { 2 } , \ldots , v _ { n }$ each holding one bit of a $k$-bit message and being connected to certain other users, then a user can reconstruct the entire message from their contacts if and only if the graph of contacts has a k-coupon coloring. The task given a graph of contacts is to determine the coupon coloring number of the graph, to maximize the length of the message that can be transmitted[3]. Clearly, $\chi _ { c } ( G ) \leq \delta ( G )$ for any graph $G$. In a $k$-coloring $c$, $a$ vertex $v$ is considered to be a bad vertex if its neighborhood lacks vertices of every color from $[k]$ and it is clear that there are no bad vertices in a coupon coloring[4].

The coupon coloring number is also referred to as the total domatic number[5]. The concept of the total domatic number of a graph was introduced by Cockayne, Dawes, and Hedetniemi in[5]. A subset $S$ of the vertex set $V (G)$ of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex from $S$. The maximum number of disjoint total dominating sets is called the total domatic number. In coupon coloring every color class must be a total dominating set in the graph. The coupon coloring number of cycle, wheel, unicyclic and bicyclic graph, complete graph, and complete $k$-partite graph were determined by Y Shi et al. in[4]. Additionally, coupon coloring has been examined in[6]and[7]. The coupon coloring number of a few binary products, including the lexicographic and cartesian products are studied in [8,9]. From the viewpoint of complexity, the problem of deciding whether a graph G has a coupon coloring at most 3 is NP-complete, even when restricted to planar graphs of maximum degree 9. It is also NP-complete to determine whether the coupon coloring number of a bipartite planar graph with bounded maximum degree is at least 3.

Snark is a connected bridgeless non-Hamiltonian cubic graph with edge chromatic number four. Every cubic graph has an edge chromatic number of either three or four according to Vizing’s theorem, hence a snark is associated with the specific case of four. The earliest and smallest known snark is the Petersen graph. In[10]Isaacs defined the Flower snark family and the Blanuˇsa families. In 1989 John J. Watkins discovered the snark with 50 vertices known as Watkins snark[11]. The Szekers snark is also a snark with 50 vertices discovered by George Szekeres in the year 1973. For a study on snarks we cite the papers [12,13,14].

For every $d$-regular graph $G$, we have as $\chi_c(G)\geq (1-o(1))\frac{d}{\log d}$$\quad \text {as} d\rightarrow \infty$, and the proportion of $d$-regular graphs $G$ for which $\chi_c(G)\leq (1+o(1))\frac{d}{\log d}$ tends to 1 as $|V(G)|\rightarrow\infty$[3]. Also for every $k\geq 3$, it is NP-complete to decide whether $dt(G)\geq k$, where $G$ is $k$-regular.Figure 1shows a cubic graph with a coupon coloring number equal to 3.

This motivation led us to explore whether any cubic graphs exist with a coupon coloring number of 2, rather than 3. Specifically, we investigated the snark graph, a well-known cubic graph, to determine if its coupon coloring number is indeed 2 or 3. We examine the coupon coloring of certain infinite families of snark graphs in Section 2 and that of some finite families in Section 3.

Figure 1.Cubic Graph

2. Coupon Coloring of Generalised Snarks

2.1. Flower snark.

Rufus Isaacs introduced the flower snark $J _ { n }$ in the year 1975 and the

.....

Read Counter : 228 Download : 314

Share Now

Coupon Coloring of Snark Graphs

Abstract

Full text article

References

Authors

Address

Contact Info

Article Sidebar

Abstract

Full text article

References

Authors

Article Details

Address

Contact Info