2460-0245Journal of the Indonesian Mathematical SocietyJIMS2460-02452086-8952IndoMS10.22342/jims.v32i2.2069Coupon Coloring of Snark GraphsRemadeviMithraIndiamithrar1729@gmail.comPanduranganRagukumarIndiaragukumar2003@gmail.comWijayantiIndah EmiliaIndonesiaind_wijayanti@ugm.ac.idDepartment of MathematicsVellore Institute of TechnologyUniversitas Gadjah Madahttps://ror.org/03ke6d638IndonesiaCorresponding author: Ragukumar Pandurangan. Email: ragukumar2003@gmail.com0105202623042026322JUNE206920862205202531012026Copyright (c) 2026 Journal of the Indonesian Mathematical Society2026Journal of the Indonesian Mathematical Societyhttps://creativecommons.org/licenses/by-nc-nd/4.0/This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
A -coupon coloring of a graph is a -coloring of G by colors such that the neighborhood of every vertex of contains vertices of all colors from . The maximum integer k for which a k-coupon coloring exists is called the coupon coloring number of , and it is denoted by . Every d-regular graph has as , and the proportion of d-regular graphs for which tends to 1 as . Coupon coloring is known to be NP-complete for k-regular graphs, even when . 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.
coupon coloring numbersnark graphregular graphThis research received the financial support provided by the Vellore Institute of Technology, Vellore, India.File created by JATS Editorhttps://jatseditor.comissue-created-year20261. INTRODUCTION
In this paper we consider the graphs that are simple, finite and undirected. Let and be the vertex set and edge set of the graph respectively. The neighbourhood of the vertex , denoted as is the set of all vertices that are adjacent to . The degree of a vertex in a graph is the number of vertices adjacent to . The minimum degree of a graph is denoted as . 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 be a graph with no isolated vertices. A -coupon coloring of G is an assignment of colors from to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from . The maximum k for which a k-coupon coloring exists is called the coupon coloring number of G, and is denoted by [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 each holding one bit of a -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, for any graph . In a -coloring , vertex is considered to be a bad vertex if its neighborhood lacks vertices of every color from 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 of the vertex set of a graph is a total dominating set if every vertex of is adjacent to at least one vertex from . 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 -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 -regular graph , we have as , and the proportion of -regular graphs for which tends to 1 as [3]. Also for every , it is NP-complete to decide whether , where is -regular. Figure 1 shows 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.
Cubic Graph
Figure 1.2. Coupon Coloring of Generalised Snarks2.1. Flower snark.
Rufus Isaacs introduced the flower snark in the year 1975 and the construction is as follows. Create copies of the star graph on 4 vertices. Label each star’s outer vertices , , and , as well as the central vertex . For , this generates a disconnected graph on vertices with edges and . Construct the -cycle by adding edges. Lastly, construct the -cycle by adding edges. By construction, the Flower snark is a cubic graph with edges and vertices. Here, must be odd for it to satisfy the necessary properties. Flower snark is shown in Figure 2.
Flower Snark
Figure 2.
Theorem 2.1. Let , for odd , be a flower snark with vertices and edges. Then .
Proof. Let be a flower snark with vertices with vertex set . Since . Assume that 3-coupon coloring exists. Let be the 3-coupon coloring. Consider , the neighboring vertices of are . Since and can get any one of the color from the set . Without loss of generality assume that . For , the neighboring vertices are , and . Since . Suppose , then , which is a contradiction since neighboring vertices of are and . Suppose , then and we get a contradiction since neighboring vertices of are and . Hence 3-coupon coloring is not possible. Now we prove 2-coupon coloring is possible. Define as follows.
Case 1: odd. Let for all and for all . Define
Consider an arbitrary vertex for . From Equation 2.1 and 2.1 and are diferent for any . Thus neighboring vertices of has 2 colors. Neighboring vertices of are and and .
For any , for all and for all . Thus neighboring vertices of also has 2 colors. Now for , consider the vertices and . Neighboring vertices of are and neighboring vertices of are . Then and will be different. Similarly in the case of . The neighboring vertices of are and neighboring vertices of are . Also and . Similarly for and .
Case 2: even. Let and . for all and for all . Now for ,
It is clear that is a coupon coloring. Thus .
2.2. Blanuˇsa Snark.
Watkins[15, 11] generalised the construction of First and Second Blanuˇsa Snarks, defining two infinite families of generalised Blanuˇsa Snarks. Let be the first family of generalised Blanuˇsa Snarks and let be the second family of generalised Blanuˇsa Snarks. The first member of is the First Blanuˇsa Snark, while the first member of is the Second Blanuˇsa Snark. In order to construct the first family, we consider the drawing of the Petersen Graph shown in the of Figure 3. In this figure, the leftmost drawing shows the first operand, and the next drawing shows the second operand. In order to construct , remove edges and from the first operand, remove vertices and from the second operand, and add edges , , , . Then we obtain the graph . Each member of , with 1 \end{document} ]]>, is obtained by the dot product , with playing the role of in the construction of . Then assign the labels for according to Figure 3. The construction of family is similar to the construction of family [16].
(a) & (b)
Figure 3
(a) & (b)
Figure 4.
Theorem 2.2.Let , be the Generalised Blanuˇsa snark of the first family of order . Then .
Proof. Let be the Generalised Blanuˇsa snark of the first family of order . Assume that the coupon coloring number of is , then there exists . Consider the vertex . The neighbors of are . Without loss of generality assume that . The neighbors of are , , and we have , .
Case 1:. Then . After considering the neighboring vertices of , we have , .
Case 1.1:. Thus we have . Since and the neighbors of must have 3 colors. We have , . When , we have a contradiction, thus and hence . Now after considering the neighbors of , we have . This will lead to a contradiction.
Case 1.2:. Then and we get and when the vertex is taken into consideration. Finally we arrive at a contradiction when the neighboring vertices of are considered and .
Case 2:. Thus . Now we consider . Then .
Case 2.1:. Then . After considering the vertex , we will arrive at a contradiction since either will become a bad vertex or will become a bad vertex.
Case 2.2:. Then we have . Now consider the vertex , we have . In both cases either will become bad vertex will become a bad vertex. Thus we get contradiction in all cases. Hence . Now it remains to show that . Define as follows. , for all and for all and .
Theorem 2.3Let , be the Generalised Blanuˇsa snark of the second family of orders . Then .
Proof. Let be the Generalised Blanuˇsa snark of the second family of the orders . We have . Assume that 3-coupon coloring exists. Consider the vertex , the neighbors of are , , and . Without loss of generality assume that . Now after considering the vertex , we have . If , we arrive at a contradiction. Thus , . The neighborhood of consists of the vertices , , and . Also . Suppose we can conclude that is a bad vertex. Thus and hence . Since , we get . Also after considering , we get which leads to a contradiction. Thus . Define as follows. for all . The remaining vertices can be colored using the color 2. Consider an arbitrary vertex where . and for all . For any vertex and , . Similarly for all vertices the neighborhood contains two colors.
3. Coupon Coloring of some more Snark families3.1. Loupikene Snark.
In 1976, Isaacs [17] introduced two families of Loupekine snarks. There are two Loupikene snarks on 22 vertices. One is the Loupikene snark and other is the Twisted Loupikene snark. Both snarks can be obtained from a basic block illustrated in Figure 5 consisting of vertices . Along with these vertices a new vertex u is introduced and joined with the vertices , and . The edge set of loupikene snark is . The edge set of Twisted Loupikene snark is .
Basic Block Bi
Figure 5.
Loupikene Snark
Figure 6.
Twisted Loupikene Snark
Figure 7.
Theorem 3.1.Let be a Loupikene snark on 22 vertices. Then .
Proof. Since . Assume that a 3-coupon coloring exists. Consider the vertex , the neighboring vertices are . Without loss of generality assume that and . After considering and then , we get , and . Otherwise neighboring vertices of will get the same color. We already have , hence the color of neighboring vertices of will be either 1 or 3. So will have the color 1 or 3. In both cases we get contradiction. Thus 3-coupon coloring is not possible. Define as follows. and for , for , and . Therefore .
Theorem 3.2.Let be a Twisted Loupikene snark on 22 vertices. Then .
Proof. Let G be a Twisted Loupikene snark on 22 vertices. We have . Suppose there exists a 3-coupon coloring . Consider the vertex , the neighbors are . Without loss of generality assume that . The neighboring vertices of are . We have two cases, either or .
Case 1:. Consider the vertex , again we have two cases. Either or .
Case 1.1:and . Similarly when we consider the vertex , we get or . Here and . Suppose and . Then , which leads to a contradiction. Thus and . After considering the neighboring vertices of and , we get and . This leads to a contradiction.
Case 1.2: and . Considering the vertex , we have two cases. Either or .
Case 1.2.1: and . The neighboring vertices of are and . We get , which leads to a contradiction.
Case 1.2.2:. Consider the vertex . Since , , we get . Also .
Case 2:. The neighbors of the vertex are and . Since , we have or .
Case 2.1:, .
Considering the vertex , we get two cases or .
Case 2.1.1:. Since we have . Also . Thus will become a bad vertex.
Case 2.1.2:. Suppose , then . Also . As a result will become a bad vertex.
Case 2.2:. The neighborhood of consist of the vertices and . Here arises two cases or . If , then and we get as bad vertex. Similarly when we get as a bad vertex. Thus 3-coupon coloring is not possible. Define as follows. and for . For we define . Also we define . Remaining vertices can be colored with 2. It can be easily that c is a coupon coloring.
3.2. Celmins-swart snark.
The Celmins-swart snarks are the two snarks on 26 vertices and 39 edges. The vertices of Celmins-swart snark are . Figure 8 and Figure 9 shows first Celmins-swart snark and second Celmins-swart snark.
First Celmins-swart snark
Figure 8.
Second Celmins-swart snark
Figure 9.
Theorem 3.3.Let G be the first Celmins-swart snark on 26 vertices. Then .
Proof. Let be the first Celmins swart snark on 26 vertices. We have .
Assume that a 3-coupon coloring exists. First consider the vertex , the neighbors are and . Without loss of generality assume that and . Now for the neighboring vertices of , we have .
Case 1:
Then . Since is the neighbor of and . Also we have . If , then which gives a contradiction. Thus and . Now for the vertex . will give rise to a contradiction. Thus and . Similarly when we consider , we get and . Finally we consider the neighbors of the vertex . Already we have . So . Suppose , we have and if we have .
Case 2 :
Then . For the neighboring vertices of .
Case 2.1 :
Then . Since and are neighbors of . If , we arrive at a contradiction. So and . Finally consider the neighbors of the vertex . We already have . When takes any color from 1 or 2 we get a contradiction.
Case 2.2 :
Then . The vertices and are neighbors of and . Thus . We get and . Now consider the vertex . Since , we get and . Finally when the vertex is taken into consideration we arrive at a contradiction. Thus 3-coupon coloringis not possible. Therefore . Define as follows. for all and . Forall other vertices we give the color 2. Thus neighbors of every vertex has 2 colors. Thus .
Theorem 3.4. Let be the second Celmins-swart snark on 26 vertices. Then .
Proof. Let be the second Celmins swart snark on 26 vertices. Since , then . Assume that a 3-coupon coloring exists. Consider the vertex , the neighboring vertices are , and . Without loss of generality assume that and . For the vertex the neighbors are and . We have , then . If we get a contradiction. So , thus . Now we get when the vertex is taken into consideration. Also we get . Avoiding the contradictions we get and . The vertices and are neighbors of and already , then .
Case 1:
Then . Now for the vertex . If we get a contradiction. Thus and . Now two of the neighbors of the vertices and have 2 colors. From this we get and . This gives us a contradiction.
Case 2:
Thus . Following the same procedure of Case 1 we get and . Finally consider the vertex . In both cases we get a contradiction. Thus 3-coupon coloring is not possible. Hence . Define as follows. . Remaining vertices can be colored with the color 2.
3.3. Double star snark.
The Double-star snark is a snark with and on 30 vertices and 45 edges. Let be the vertices of , where . The link edges of forms -cycles with vertices and .
Double Star Snark
Figure 10.
Theorem 3.5. Let with and be a double star snark on 30 vertices. Then .
Proof. Let with and be a Double star snark on 30 vertices. We have . Let us assume that a 3-coupon coloring exists. Consider the vertex the neighbors are and . Without loss of generality assume that and . One of the neighbors of is assigned with color 1. Thus . When we get a contradiction. Similarly when we consider the neighbors of , we get and . Now we have ,. Thus . Since . When , we arrive at a contradiction. Thus . Consider the vertex , and and hence . Similarly when the vertex is taken into consideration we will get a contradiction. Thus . Define as follows. Let for all . Remaining vertices can be colored with 1. Thus .
3.4. Watkins Snark.
Watkins snark graph is a snark in graph theory, discovered by John J. Watkins[11] in 1989. Watkins snark has 50 vertices and 75 edges. The construction of Watkins snark includes 5 blocks with vertices where . The edge set of Watkins snark is .
Theorem 3.6. Let G be Watkins snark on 50 vertices. Then .
Proof. Let be Watkins snark on 50 vertices. Since . Assume that a 3-coupon coloring exists. Consider the vertex , the neighboring vertices are . Without loss of generality and . Neighboring vertices of are . Since . Suppose then and will have same color 2 and neighboring vertices are and . Thus , which implies and . Now consider and its neighboring vertices. We have . Since neighboring vertices of includes and , we get a contradiction when . Contradiction also arises when . Thus 3-coupon coloring is not possible. Define as follows. For all , and . Consider an arbitrary vertex where , and . In case of , . Similarly for every other vertex. Consequently, it is clear that is a coupon coloring. Thus .
Watkins Snark
Figure 11.3.5. Szekeres Snark.
The Szekeres snark is a snark with 50 vertices and 75 edges discovered by George Szekeres [18] in the year 1973. The construction of Szekeres snark has 5 blocks with vertices where . The edge set of Szekers snark is .
Theorem 3.7. Let be a Szekers snark with 50 vertices and 75 edges. Then .
Proof. Let be a Szekers snark with 50 vertices and 75 edges. Since , it follows that . Suppose , then a 3-coupon coloring exists.Consider the vertex . Without loss of generality assume that and . For the neighbours of .
Case 1:
Thus . Consider the vertex , . If , we get a contradiction since the neighborhood of has 2 vertex with same color. Therefore and . Similarly after considering , we get . Now consider the neighboring vertices of . This leads to a contradiction.
Case 2:
This . We get a contradiction similar to Case 1. Thus .
Define as follows. and for all .
Szekeres Snark
Figure 12.4. CONCLUSION AND FUTURE SCOPE
In this paper, we explored that coupon coloring number of various finite and infinite families of snarks is 2 even though snark graphs are cubic. In future, the coupon coloring number of more snark families can be investigated.
Data Availability Statement.
No new data were created or analyzed in this study.
Declarations.
The authors declare no conflict of interest.
Author Contributions.
All authors have read and agreed to the published version of the manuscript. All authors contributed equally to this paper. All authors reviewed the manuscript.
Acknowledgement.
The first author expresses her gratitude to Vellore Institute of Technology, Vellore, India for providing financial support that enabled the author to carry out the research work.
REFERENCESGraph theory with applicationsBondyJ.A.MurtyU.S.R.1976Introduction to graph theoryWestD.B.2001On coupon colorings of graphsDiscrete Applied Mathematics193ChenB.KimJ.H.TaitM.VerstraeteJ.201594-101,10.1016/j.dam.2015.04.026Coupon coloring of some special graphsJournal of Combinatorial Optimization33ShiY.WeiM.YueJ.ZhaoY.2017156-164,10.1007/s10878-015-9942-2Total domination in graphsNetworks103CockayneE.J.DawesR.HedetniemiS.T.1980211-219,10.1002/net.3230100304Coupon coloring of cographsApplied Mathematics and Computation308ChenH.JinZ.201790-95,10.1016/j.amc.2017.03.023Coupon-coloring and total domination in hamiltonian planar triangulationsGraphs and Combinatorics34NagyZ.L.20181385-1394,On coupon coloring of cartesian product of some graphsAlgorithms and Discrete Applied Mathematics: 7th International Conference, CALDAM 2021Proceedings 7FrancisP.RajendraprasadD.2021309-316,SpringerRupnagar, India10.1007/978-3-030-67899-9Coupon coloring of lexicographic product of graphsThe Art of Discrete and Applied Mathematics61ThankachanR.RajamaniP.20231-03,10.26493/2590-9770.1507.dc5Infinite families of nontrivial trivalent graphs which are not tait colorableThe American Mathematical Monthly823IsaacsR.1975221-239,10.1080/00029890.1975.11993805SnarksAnnals of the New York Academy of Sciences5761WatkinsJ.J.1989606-622,10.1111/j.1749-6632.1989.tb16441.xThe total-chromatic number of some families of snarksDiscrete Mathematics31112CamposC.DantasS.MelloC.P.2011984-988,10.1016/j.disc.2011.02.013Special classes of snarksActa Applicandae Mathematica76CavicchioliA.MurgoloT.RuiniB.SpaggiariF.200357-88,10.1023/A:1022864000162On coloring problems of snark familiesElectronic Notes in Discrete Mathematics37SasakiD.DantasS.FigueiredoC.M.201145-50,10.1016/j.endm.2011.05.009On the construction of snarksArs Combin16WatkinsJ.J.1983111-124,Developments of fulkerson’s conjectureGalvaoK.K.2013Institute of Computing, University of CampinasLoupekhine’s snarks: a bifamily of non-tait-colorable graphsJ. Combin. Theory BIsaacsR.197610.2307/2319844Polyhedral decompositions of cubic graphsBulletin of the Australian Mathematical Society83SzekeresG.1973367-387,10.1017/S0004972700042660