The star-chromatic number of snarks and its variants

1 Introduction

Let G be a connected graph, denoted by G (V, E), where V (G) represents the vertices or nodes of the graph and E (G) represents the edges or connections between the vertices. A vertex’s degree is determined by the number of edges connected to it. This paper specifically focuses on finite, simple, and undirected graphs. A proper vertex coloring of a graph G is a color assignment, denoted as c, to its vertices in such a way that if two vertices u and v are adjacent, then c (u) is not equal to c (v). The chromatic number of a graph G, represented as χ (G), is the minimum number of colors required to achieve the proper coloring. By imposing conditions, various parameters on coloring have been introduced. In the context of proper coloring, it is considered as star coloring if every path of length 3 within the graph is assigned at least 3 distinct colors. Also, the induced subgraph of any bicolor partition is a forest whose components are stars. The star chromatic number of a graph G, denoted as χ _s  (G), is the minimum number of colors needed to accomplish the star coloring of the given graph G. Denote {1, 2, 3 … x} as [  [x]  ].

Girunbaum [1] first introduced star coloring in 1973. This parameter is investigated for cycles, trees, complete bipartite graphs, two-dimensional grids and outerplanar graphs [2]. Albertson et al. [3] demonstrated that even if the graph G is both planar and bipartite, the computational problem of determining whether G can be star-colored using only three colors is NP-complete. The connection between the conventional chromatic number and this particular variant is explored in [4]. The star chromatic number for bipartite planar graphs was provided by Kierstead et al. [5]. Coleman and More [6] proved that for bipartite graphs, it is NP-hard. Yuehua Bu et al. [7] analyzed the correlation between χ _s  (G) and its maximal average degree. This problem was investigated for cographs in [8]. A non-regular sub-cubic graph or cubic graph with a minimum girth of six was discussed in [9]. Karthick obtained the bound for star chromatic number in terms of clique number in 2018 [10], along with the tight bound for perfect graphs. This problem was investigated for the Cartesian product of cycle with path and cycle with cycle recently in [11]. In [12], the star coloring of regular graphs and bounded degree graphs was discussed. In [13], the star coloring of outerplanar bipartite graphs was discussed. In [14], Shalu and Sandhya proved that 4α (G) is the limited set of χ _s  (G) for a graph G with girth at least five. The other results and findings regarding the star coloring of graphs are referred to [15–18]. In a recent paper by Cary [19], it was proven that the dominator chromatic number of each oriented tree remains invariant under reversal of orientation. In [20], chromatic completion and stability regarding Johan coloring were discussed. In a recent paper [21], a new notion called the total chromatic vertex stress of a graph was introduced. This novel concept sheds light on the interplay between graph coloring and stress within the vertices. It also presents the results for certain tree families and other 2-colorable graphs.

In this article, we explore the star coloring scheme of Goldberg snarks, twisted Goldberg snarks, flower snarks and their associated graphs and how these specific graph families can be colored under the constraints imposed by the star coloring definition.

2 Applications

Star coloring is employed in evaluating sparse Hessian matrices. For the estimation of sparse Hessian matrices, two methods are employed, namely, the substitution method and the direct method. Refer [22, 23] to provide detailed insights into coloring problems associated with sparse derivative matrices. Both processes involve matrix compression implicitly. In the direct method, coloring variants used include distance-two coloring and star coloring. Star coloring gives better compression between the two.

Interconnection networks are used in various computing systems, such as parallel and distributed systems, multiprocessors, and data centers. The objective of star coloring in interconnection networks is primarily to ensure efficient and conflict-free communication among network nodes while minimizing resource usage and maintaining network connectivity. The star coloring technique aims to address specific challenges associated with routing and communication in these networks. One of the primary objectives of star coloring is to enable conflict-free communication among nodes in the interconnection network. By assigning colors to network nodes in such a way that adjacent nodes have different colors, star coloring ensures that no two neighboring nodes attempt to communicate simultaneously, thus avoiding contention and potential message collisions.

In the problem of minimization of channel interference, star coloring helps to minimize channel interference by ensuring that nodes using the same communication channel (or link) have distinct colors. This reduces the likelihood of interference and improves the overall reliability of communication and performance within the network.

In energy-constrained environments, such as mobile computing devices and wireless sensor networks, energy-efficient communication is crucial. Star coloring algorithms can be optimized to minimize energy consumption by reducing the number of active communication channels and optimizing message routing paths.

3 Snark

The search for counterexamples to the four-color conjecture has significantly influenced and motivated the study of specific types of graphs called snarks. Gardner coined the term ‘snark’ to refer to bridgeless cubic graphs characterized by a chromatic index of 4. The study of snarks has become a fascinating area of graph theory, and various properties and classifications of snarks have been explored. Snarks have connections to various topics, including the four-color theorem, graph coloring, and structural properties of cubic graphs. Various widely recognized conjectures have minimal counterexamples in the form of snarks, which contributes to the significance of these graphs. The Petersen graph is notably the earliest and smallest identified example of a snark. The decomposition of snarks has been discussed [24] by Cameron et al. in 1987. Some interesting properties of snark have been studied in [25, 26]. In 2003 [27], special classes of snarks and the connection between the snark family and some significant conjectures have been discussed. In 2006, the circular chromatic index of flower snark was discussed [28]. The total chromatic number and sigma chromatic number were respectively investigated in [29] and [30] for snark and its three variants. Some important properties about snark and girth parameters were reported in [31, 32]. The equitable chromatic number and total chromatic number of infinite families of snarks were presented in [33].

3.1 Flower Snarks

The primary and paramount focus in medical information systems revolves around the matter of protecting the electronic health records of patients. There are several information systems in the literature [34]. To protect a healthcare industry’s computer network against attacks on its nodes and links, it is necessary to deploy some pattern of saving the data in such a way that others do not steal the information. A flower snark topologies are appealing networks that have the potential to serve as structures for highly parallel computers. The healthcare industry is frequently the primary focus of cyber thieves, who target and exploit its vulnerabilities. Therefore, it is crucial to restrain medical cyber piracy and safeguard the network infrastructure that sustains it [35]. The mathematical representation of cyberspace can be achieved through graph theory, as the fundamental structure of a graph is well-suited for capturing the interconnected nature of computer networks. Nodes can be linked to many physical or virtual systems, including routers and internet infrastructure. Edges can symbolise connections or the flow of information between nodes [36]. A graph-based strategy in cybersecurity can enhance the effectiveness and capability of security operations teams by creating a system of records and intelligence that informs future threat detection. Issacs first introduced one such graph model named flower snark [37] in the year 1975 is discussed in this paper. The network proposed for the medication process using technology and the corresponding flower snark J₅ are depicted in Fig. 1(a) and (b), respectively.

OPEN IN VIEWER

Fig. 1

(a) Medication process using technology; (b) Flower snarkJ₅.

A flower snark is a cubic graph that is 3-regular, bridgeless, and connected. It is coined by J _n , with order 4n and size 6n. The vertex set V (J _n ) is described with elements labeled as {a _i , b _i , c _i , d _i  : i ∈ [  [n]  ]}, where the vertices {a _i  : i ∈ [  [n]  ]} referred to as central vertices. The flower snark J _n contains two cycles, namely inner and outer cycles of length n and 2n, respectively. The inner cycle is induced by the vertices {b _i  : i ∈ [  [n]  ]} and the outer cycle is induced by the vertices {c _i  : i ∈ [  [n]  ]} ∪ {d _i  : i ∈ [  [n]  ]}. The edge set E (J _n ) is described with elements labeled as E (J _n ) = {a _i b _i , a _i c _i , a _i d _i , b _i b_i+1, c _i c_i+1, d _i d_i+1 : i ∈ [  [n]  ]}, where the edges c _n c₁ and d _n d₁ are substituted with c _n d₁ and d _n c₁ respectively. Indices are computed modulo n. Figure 2 gives the even version of it. The crossing number for this class has been investigated in [38].

OPEN IN VIEWER

Fig. 2

Flower snark J₆.

3.2 Twisted Goldberg Snarks and Goldberg

Rearranging some of the connections in the network may increase the performance of the processor or network in terms of data transmission and broadcasting and make it less time-consuming to transfer data from one end to another. Swapping of connections in the network has a rich literature in network science. For example, Fig. 3 depicts the hypercube and its twisted version. One can examine from Fig. 3 that the diameter of a hypercube is 3 and that of the twisted cube is 2.

OPEN IN VIEWER

Fig. 3

(a) Hypercube; (b) Twisted cube.

A few examples are Möbius ladders, 0 Möbius cubes, 1 Möbius cubes, twisted cubes and crossed cubes. The diameter of the Möbius cubes is considerably smaller than the traditional cube (hypercube). Consequently, we have less transmission for the graph with swapped edges than the original one. Figure 4 depicts the comparative study on the diameter of certain cubes made by twisting the edges of a cube and its original version. All these aspects are similar to the case of crossed cubes. In the case of Möbius ladders, it has been utilised as the structure of a superconducting ring in studies to investigate the impact of conductor topology on electron interactions [39].

OPEN IN VIEWER

Fig. 4

Comparative analysis of the diameter of various cubes by twisting the edges.

These structures are also utilised in computer engineering for integer programming methods related to linear ordering and set packing difficulties. Specific arrangements in these issues can define aspects of the polytope that describe a linear programming relaxation. These aspects are known as Möbius ladder constraints [40].

The first molecular structures that is similar to Möbius ladder were made by Walba et al. [41]. Since then, the structure has attracted interest in the domains of chemical stereography and chemistry, mainly because of its similarities to the ladder-like structure of DNA molecules. In [42], Flapan investigates the symmetry of embeddings of Möbius ladders in ℝ 3 . Any three-dimensional embedding of an odd-rung Möbius ladder is topologically chiral, which means that it cannot be continuously deformed into its mirror image without any edges passing through one another. In contrast, it is possible to embed any Möbius ladders with an even number of rungs inside ℝ 3 in a way that makes it possible to convert them into their mirror counterparts. For this reason, we try to investigate the original Goldberg snarks and their twisted variant, which is known as twisted Goldberg snarks.

The Goldberg snarks were discovered by Goldberg in [43]. The Goldberg snark G _n is constructed using the basic block B _i whose vertices are V ( B i ) = { a i , b i , c i , c i ′ , c i ″ , d i , d i ′ , d i ″ } and E (B _i ) = { a i b i , a i c i , a i d i , c i c i ′ , d i d i ′ , d i c i ″ , c i d i ″ , c i ′ d i ′ , c i ″ d i ″ } . The edges { d i - 1 ″ c i ″ , d i - 1 ′ c i ′ , b i - 1 b i } represents the set of link edges.

The construction of a link graph denoted as L _i , which involves connecting basic blocks B_i-1 and B _i using certain edges { d i - 1 ″ c i ″ , d i - 1 ′ c i ′ , b i - 1 b i } . The vertex set of L _i , denoted V (L _i ), is the union of the vertex sets of B _i and B_i-1 that is V (L _i ) = V (B _i ) ∪ V (B_i-1). The edge set of L _i , denoted E (L _i ), is the union of the edge sets of B _i and B_i-1 along with the specified additional edges { d i - 1 ″ c i ″ , d i - 1 ′ c i ′ , b i - 1 b i } . Therefore, E ( L i ) = E ( B i - 1 ) ∪ E ( B i ) ∪ { d i - 1 ″ c i ″ , d i - 1 ′ c i ′ , b i - 1 b i } .

This is described in Fig. 5.

OPEN IN VIEWER

Fig. 5

Link graph in G _n , in which the blocks B_i-1 and B _i appears consecutively.

The twisted Goldberg snark, denoted as TG _n , is obtained by similarly rearranging the edges of G _n . The notation TG _n suggests that this is a transformed graph derived from, G _n and TG _n for n odd and even are depicted in Fig. 6 and Fig. 7 respectively. In symbolic terms, if E (G _n ) represents the edge set of G _n , then the edge replacement operation can be expressed as: E ( TG n ) = ( E ( G n ) \ { c 1 ′ d n ′ , c 1 ″ d n ″ } ) ∪ { c 1 ′ d n ″ , c 1 ″ d n ′ } . This operation essentially involves removing the original edges and adding the replacement edges, resulting in the transformed graph TG _n . Both G _n and TG _n are graphs with 8n vertices and 12n edges. The feedback number for this class G _n and TG _n have been investigated in [44].

OPEN IN VIEWER

Fig. 6

(a) G₃; (b) TG₃.

OPEN IN VIEWER

Fig. 7

(a) G₄; (b) TG₄.

In this section, we will be discussing the snark and its derived graphs, which happen to be cubic graphs, so we will begin by stating some essential bounds regarding the star coloring of cubic graphs.

Theorem 1. [45] For a cubic graph G, 4 ≤ χ _s  (G) ≤6.

In the above theorem, the lower bound is achieved by the complete graph K₄ while the upper bound is achieved by Wagner’s graph, commonly referred to as the 8-vertex Möbius ladder graph M₈.

Theorem 2. For n ≥ 3, χ _s  (J _n ) =4.

Proof. Since, J _n is a cubic graph and by Theorem 1, χ _s  (J _n ) ≥4. For χ _s  (J _n ) ≤4, let { C 1 , C 2 , C 3 , C 4 } be the set of color to star color the vertices of J _n . The coloring argument is divided into three cases.

Case 1: n ≡ 0 (mod 3)

f ( u ) = { C 1 , u ∈ { b 3 i - 2 , c 3 i - 2 , d 3 i - 2 : i ∈ [ [ n 3 ] ] } ∥ C 2 , u ∈ { b 3 i - 1 , c 3 i - 1 , d 3 i - 1 : i ∈ [ [ n 3 ] ] } ∥ C 3 , u ∈ { b 3 i , c 3 i , d 3 i : i ∈ [ [ n 3 ] ] } ∥ C 4 , u ∈ { a i : i ∈ [ [ n ] ] }

Case 2: n ≡ 1 (mod 3) f ( u ) = C 1 , u ∈ { b 3 i - 2 , c 3 i - 2 , d 3 i - 2 : i ∈ [ [ n - 1 3 ] ] } f ( u ) = C 2 , u ∈ { b 3 i - 1 , c 3 i - 1 , d 3 i - 1 : i ∈ [ [ n - 1 3 ] ] } ∪ { b n , c n , d n } , f ( u ) = C 3 , u ∈ { b 3 i , c 3 i , d 3 i : i ∈ [ [ n - 1 3 ] ] } , f ( u ) = C 4 , u ∈ { a i : i ∈ [ [ n ] ] } .

Case 3: n ≡ 2 (mod 3) For n = 5, f ( u ) = C 1 : u ∈ { b 1 , c 1 , d 1 , b 3 , c 3 , d 3 } , f ( u ) = C 2 : u ∈ { b 2 , c 2 , d 2 , a 4 , a 5 } , f ( u ) = C 3 , u ∈ { a 1 , a 2 , b 4 , c 4 , d 4 } , f ( u ) = C 4 , u ∈ { a 3 , b 5 , c 5 , d 5 } .

See Fig. 8.

OPEN IN VIEWER

Fig. 8

Star coloring scheme of J₅.

Case 3.1: When n ≠ 5 f ( u ) = { C 1 , u ∈ { b 3 i - 2 , c 3 i - 2 , d 3 i - 2 : i ∈ [ [ n - 5 3 ] ] } ∪ { b n - 3 , c n - 3 , d n - 3 } C 2 , u ∈ { b 3 i - 1 , c 3 i - 1 , d 3 i - 1 : i ∈ [ [ n - 5 3 ] ] } ∪ { b n - 4 , b n - 2 , b n , c n - 4 , c n - 2 , c n , d n - 4 , d n - 2 , d n } C 3 , u ∈ { b 3 i , c 3 i , d 3 i : i ∈ [ [ n - 5 3 ] ] } ∪ { b n - 1 , c n - 1 , d n - 1 } C 4 , u ∈ { a i : i ∈ [ [ n ] ] }

In all the above cases, we used only four colors to star color the graph J _n , which implies χ _s  (J _n ) ≤4. Therefore, χ _s  (J _n ) =4.□

Theorem 3. For n ≥ 3, n is odd and G ∈ {G _n , TG _n } , χ _s  (G) =4.

Proof. By Theorem 1, χ _s  (G) ≥4. Let { C 1 , C 2 , C 3 , C 4 } be the colors used to star color the vertices of G, and the coloring scheme is given as follows: Case 1: For n = 3 f ( u ) = { C 1 : u ∈ { a 2 , b 1 , d 3 , c 3 ′ , d 1 ′ , d 1 ″ } C 2 : u ∈ { a 3 , b 2 , d 1 , c 1 ′ , d 2 ′ , d 2 ″ } C 3 : u ∈ { a 1 , b 3 , d 2 , c 2 ′ , d 3 ′ , d 3 ″ } C 4 : u ∈ { c 1 , c 2 , c 3 , c 1 ″ , c 2 ″ , c 3 ″ }

The edge set E ( TG 3 ) = ( E ( G 3 ) \ { c 1 ″ d 3 ″ , c 1 ′ d 3 ′ } ) ∪ { c 1 ″ d 3 ′ , c 1 ′ d 3 ″ } . It is observed that the connection pattern of TG₃ differs only by two edges that of G₃, which does not affect the coloring scheme of TG₃, which implies G₃ and TG₃ has the same coloring pattern.

See Fig. 9(a) and 9 (b). This concludes χ _s  (G) =4.

OPEN IN VIEWER

Fig. 9

(a) Star coloring scheme of G₃; (b) Star coloring scheme of TG₃.

Case 2: For n = 5 f ( u ) = { C 1 , u ∈ { d 1 ′ , d 1 ″ , c 2 , d 2 , b 3 , d 3 ′ , d 3 ″ , a 4 , b 5 , c 5 ′ , c 5 ″ } C 2 , u ∈ { a 1 , c 2 ′ , c 2 ″ , c 3 ′ , c 3 ″ , b 4 , c 4 ′ , c 4 ″ , d 5 ′ , d 5 ″ } C 3 , u ∈ { b 1 , c 1 ′ , c 1 ″ , a 2 , c 3 , d 3 , d 4 ′ , d 4 ″ , c 5 , d 5 } C 4 , u ∈ { c 1 , d 1 , b 2 , d 2 ′ , d 2 ″ , a 3 , c 4 , d 4 , a 5 }

The edge set E ( TG 5 ) = ( E ( G 5 ) \ { c 1 ′ d 5 ′ , c 1 ″ d 5 ″ } ) ∪ { c 1 ′ d 5 ″ , c 1 ″ d 5 ′ } . It is observed that the connection pattern of TG₅ differs only by two edges that of G₅, which does not affect the coloring scheme of TG₅, which implies G₅ and TG₅ has the same coloring pattern. See Fig. 10(a) and 10 (b), and the bicolor partition of G₅ is given in Fig. 11. This concludes χ _s  (G) =4.

OPEN IN VIEWER

Fig. 10

(a) Star coloring scheme of G₅; (b) Star coloring scheme of TG₅.

OPEN IN VIEWER

Fig. 11

Bicolor partition of G₅.

Case 3: For n ≥ 7

Case 3.1: n = 4t + 3, t = 1, 2, 3… For i ∈ [ [ n + 1 4 ] ] , f ( u ) = { C 1 , u ∈ { b 4 i - 3 , d 4 i - 3 ′ , d 4 i - 3 ″ , a 4 i - 2 } C 2 , u ∈ { d 4 i - 3 , c 4 i - 3 ′ , b 4 i - 2 , d 4 i - 2 ′ , d 4 i - 2 ″ } C 3 , u ∈ { c 4 i - 3 , c 4 i - 3 ″ , c 4 i - 2 ′ , d 4 i - 2 } C 4 , u ∈ { a 4 i - 3 , c 4 i - 2 , c 4 i - 2 ″ }

For i ∈ [ [ n - 3 4 ] ] , f ( u ) = { C 1 , u ∈ { c 4 i - 1 , c 4 i - 1 ″ , d 4 i , c 4 i ′ } C 2 , u ∈ { a 4 i - 1 , c 4 i , c 4 i ″ } C 3 , u ∈ { b 4 i - 1 , d 4 i - 1 ′ , d 4 i - 1 ″ , a 4 i } C 4 , u ∈ { d 4 i - 1 , c 4 i - 1 ′ , b 4 i , d 4 i ′ , d 4 i ″ }

f ( u ) = { C 1 , u ∈ { d n , c n ′ } C 2 , u ∈ { c n } C 3 , u ∈ { a n , c n ″ } C 4 , u ∈ { b n , d n ′ , d n ″ }

Case 3.2: n = 4t + 5, t = 1, 2, 3…

Case 3.2.1: n ≡ 0  (mod 3) For i ∈ [ [ n 3 ] ] , f ( u ) = { C 1 , u ∈ { a 3 i - 1 , b 3 i - 2 , c 3 i ′ , d 3 i , d 3 i - 2 ′ , d 3 i - 2 ″ } C 2 , u ∈ { a 3 i , b 3 i - 1 , c 3 i - 2 ′ , d 3 i - 1 ′ , d 3 i - 1 ″ , d 3 i - 2 } C 3 , u ∈ { a 3 i - 2 , , b 3 i , c 3 i - 1 ′ , d 3 i - 1 , d 3 i ′ , d 3 i ″ } C 4 , u ∈ { c 3 i - 2 ″ , c 3 i - 2 , c 3 i - 1 ″ , c 3 i - 1 , c 3 i ″ , c 3 i }

Case 3.2.2: nnotequiv0  (mod 3). For i ∈ [ [ n - 9 4 ] ]

f ( u ) = { C 1 , u ∈ { b 4 i - 3 , d 4 i - 3 ′ , d 4 i - 3 ″ , a 4 i - 2 , c 4 i - 1 , c 4 i - 1 ″ , d 4 i , c 4 i ′ } C 2 , u ∈ { d 4 i - 3 , c 4 i - 3 ′ , b 4 i - 2 , d 4 i - 2 ′ , d 4 i - 2 ″ , a 4 i - 1 , c 4 i , c 4 i ″ } C 3 , u ∈ { c 4 i - 3 , c 4 i - 3 ″ , c 4 i - 2 ′ , d 4 i - 2 , b 4 i - 1 , d 4 i - 1 ′ , d 4 i - 1 ″ , a 4 i } C 4 , u ∈ { a 4 i - 3 , c 4 i - 2 , c 4 i - 2 ″ , c 4 i - 1 ′ , d 4 i - 1 , b 4 i , d 4 i ′ , d 4 i ″ }

f ( u ) = { C 1 , u ∈ { b n - 8 , d n - 8 ′ , d n - 8 ″ , b n - 5 , d n - 5 ′ , d n - 5 ″ , b n - 2 , d n - 2 ′ , d n - 2 ″ } C 2 , u ∈ { d n - 8 , c n - 8 ′ , d n - 5 , c n - 5 ′ , d n - 2 , c n - 2 ′ } C 3 , u ∈ { c n - 8 , c n - 8 ″ , c n - 5 , c n - 5 ″ , c n - 2 , c n - 2 ″ } C 4 , u ∈ { a n - 8 , a n - 5 , a n - 2 }

f ( u ) = { C 1 , u ∈ { a n - 7 , a n - 4 , a n - 1 } ∥ C 2 , u ∈ { b n - 7 , d n - 7 ′ , d n - 7 ″ , b n - 4 , d n - 4 ″ , d n - 4 ′ , b n - 1 , d n - 1 ″ , d n - 1 ′ } ∥ C 3 , u ∈ { c n - 7 ′ , d n - 7 , c n - 4 ′ , c n - 1 ′ , d n - 4 , d n - 1 } ∥ C 4 , u ∈ { c n - 7 , c n - 7 ″ , c n - 4 , c n - 4 ″ , c n - 1 , c n - 1 ″ }

f ( u ) = { C 1 , u ∈ { d n - 6 , c n - 6 ′ , d n - 3 , c n - 3 ′ , d n , c n ′ } ∥ C 2 , u ∈ { c n - 6 , c n - 3 , c n } ∥ C 3 , u ∈ { a n - 6 , c n - 6 ″ , a n - 3 , c n - 3 ″ , a n , c n ″ } ∥ C 4 , u ∈ { b n - 6 , d n - 6 ′ , d n - 6 ″ , b n - 3 , d n - 3 ′ , d n - 3 ″ , b n , d n ′ , d n ″ }

Since, E ( TG n ) = ( E ( G n ) \ { c n ′ d 1 ′ , c n ″ d 1 ″ } ) ∪ { c n ′ d 1 ″ , c n ″ d 1 ′ } . Also, the coloring scheme of TG _n is same as G _n . Each vertex is assigned one of the four colors. Specifically, the coloring scheme ensures that no P₄ forms a 2-colored subgraph. This implies that there are only four colors required to star color G _n and TG _n , for n is odd and G ∈ {G _n , TG _n }. Therefore, χ _s  (G) =4. □

Theorem 4. For n ≥ 4, n is even and G ∈ {G _n , TG _n }, χ _s  (G) =4.

Proof. Since, G _n is a cubic graph and by Theorem 1, χ _s  (G _n ) ≥4. We denote the set of colors used to star color the vertices of a graph G as { C 1 , C 2 , C 3 , C 4 } . The coloring rule is given as follows.

Case 1: n ≡ 0  (mod 4) For i ∈ [ [ n 4 ] ] ,

f ( u ) = { C 1 , u ∈ { b 4 i - 3 , d 4 i - 3 ′ , d 4 i - 3 ″ , a 4 i - 2 , c 4 i - 1 , c 4 i - 1 ″ , d 4 i , c 4 i ′ } C 2 , u ∈ { d 4 i - 3 , c 4 i - 3 ′ , b 4 i - 2 , d 4 i - 2 ′ , a 4 i - 1 , d 4 i - 2 ″ , c 4 i , c 4 i ″ } C 3 , u ∈ { c 4 i - 3 , c 4 i - 3 ″ , c 4 i - 2 ′ , d 4 i - 2 , b 4 i - 1 , d 4 i - 1 ′ , d 4 i - 1 ″ , a 4 i } C 4 , u ∈ { a 4 i - 3 , c 4 i - 2 , c 4 i - 2 ″ , d 4 i - 1 , c 4 i - 1 ′ , b 4 i , d 4 i ′ , d 4 i ″ }

Case 2: nnotequiv0  (mod 4)

Case 2.1: n ≡ 0  (mod 3) For i ∈ [ [ n 3 ] ] , f ( u ) = { C 1 , u ∈ { a 3 i - 1 , b 3 i - 2 , c 3 i ′ , d 3 i , d 3 i - 2 ′ , d 3 i - 2 ″ } ∥ C 2 , u ∈ { a 3 i , b 3 i - 1 , c 3 i - 2 ′ , d 3 i - 2 , d 3 i - 1 ′ , d 3 i - 1 ″ } ∥ C 3 , u ∈ { a 3 i - 2 , b 3 i , c 3 i - 1 ′ , d 3 i - 1 , d 3 i ′ , d 3 i ″ } ∥ C 4 , u ∈ { c 3 i - 2 , c 3 i - 1 , c 3 i , c 3 i - 2 ″ , c 3 i - 1 ″ , c 3 i ″ }

Case 2.2: nnotequiv0  (mod 3) For i ∈ [ [ n - 6 4 ] ] , f ( u ) = { C 1 , u ∈ { b 4 i - 3 , d 4 i - 3 ′ , d 4 i - 3 ″ , a 4 i - 2 , c 4 i - 1 , c 4 i - 1 ″ , d 4 i , c 4 i ′ } ∥ C 2 , u ∈ { d 4 i - 3 , c 4 i - 3 ′ , b 4 i - 2 , d 4 i - 2 ′ , d 4 i - 2 ″ , a 4 i - 1 , c 4 i , c 4 i ″ } ∥ C 3 , u ∈ { c 4 i - 3 , c 4 i - 3 ″ , c 4 i - 2 ′ , d 4 i - 2 , b 4 i - 1 , d 4 i - 1 ′ , d 4 i - 1 ″ , a 4 i } ∥ C 4 , u ∈ { a 4 i - 3 , c 4 i - 2 , c 4 i - 2 ″ , c 4 i - 1 ′ , d 4 i - 1 , b 4 i , d 4 i ′ , d 4 i ″ }

f ( u ) = { C 1 , u ∈ { b n - 5 , d n - 5 ′ , d n - 5 ″ , b n - 2 , d n - 2 ′ , d n - 2 ″ } ∥ C 2 , u ∈ { d n - 5 , c n - 5 ′ , d n - 2 , c n - 2 ′ } ∥ C 3 , u ∈ { c n - 5 , c n - 5 ″ , c n - 2 , c n - 2 ″ } ∥ C 4 , u ∈ { a n - 5 , a n - 2 } f ( u ) = { C 1 , u ∈ { a n - 4 , a n - 1 } ∥ C 2 , u ∈ { b n - 4 , d n - 4 ′ , d n - 4 ″ , b n - 1 , d n - 1 ′ , d n - 1 ″ } ∥ C 3 , u ∈ { c n - 4 ′ , d n - 4 , c n - 1 ′ , d n - 1 } ∥ C 4 , u ∈ { c n - 4 , c n - 4 ″ , c n - 1 , c n - 1 ″ } f ( u ) = { C 1 , u ∈ { d n - 3 , c n - 3 ′ , d n , c n ′ } ∥ C 2 , u ∈ { c n - 3 , c n } ∥ C 3 , u ∈ { a n - 3 , c n - 3 ″ , a n , c n ″ } ∥ C 4 , u ∈ { b n - 3 , d n - 3 ′ , d n - 3 ″ , b n , d n ′ , d n ″ }

In all the above cases, we used only four colors to star color the graph G _n , which implies χ _s  (G _n ) ≤4. Therefore, χ _s  (G _n ) =4, for n ≥ 4 and n is even. Since, E ( TG n ) = ( E ( G n ) \ { c n ′ d 1 ′ , c n ″ d 1 ″ } ) ∪ { c n ′ d 1 ″ , c n ″ d 1 ′ } . Also, the coloring scheme of TG _n is same as G _n . Each vertex is assigned one of the four colors. Specifically, the coloring scheme ensures that no P₄ forms a 2-colored subgraph. This implies that there are only four colors required to star color G _n and TG _n , for n is even and G ∈ {G _n , TG _n }. Therefore, χ _s  (G) =4.

The paper asserts that the star-chromatic number is four for the snark and its variants. The demonstration extends to the related graphs of Goldberg snarks, twisted Goldberg snarks and flower snarks. This suggests that not only the original snarks but also certain modifications or variations within these families have a star chromatic number of four. This finding not only sheds light on the inherent properties of these graph families but also opens avenues for further investigation. Future research could explore the implications of our results in various areas of graph theory and combinatorics. For instance, investigating the relationships between the star-chromatic number and other graph parameters could lead to deeper insights into the structural properties of these families of snarks. Additionally, exploring the computational aspects of star-coloring algorithms for these graphs could have practical implications for network design and optimization. Moreover, our recursive procedures for constructing star-colorings present a systematic framework that could be extended to color other classes of graphs characterized by recursive constructions. Exploring the applicability of our method to various graph classes could lead to the improvement of efficient colouring algorithms for a wide range of graph structures. Overall, our findings contribute to the broader understanding of this parameter of snark families and provide a foundation for future research endeavours.