The star-chromatic number of snarks and its variants

Abstract

The star coloring problem is a specialized form of vertex coloring that arises in certain computational contexts, such as when computing Hessians using automatic differentiation or finite differencing. This problem is particularly relevant when exploiting both sparsity and symmetry in the computation. Automatic differentiation is a technique used to compute derivatives numerically, and finite differencing is another approach for approximating derivatives. In these computations, sparsity (a small number of non-zero elements in a matrix) and symmetry (certain patterns in the structure of the matrix) are often exploited to optimize efficiency. A proper vertex coloring of the graph G is considered as star coloring if it uses at least three different colors for every path of length three. 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. This paper focuses on determining χ_s (G) for graphs belonging to the family of snarks and their variants.

Keywords

Star coloring snarks Goldberg snarks twisted Goldberg snarks

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.

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_ib_i, a_ic_i, a_id_i, b_ib_i+1, c_ic_i+1, d_id_i+1 : i ∈ [ [n] ]}, where the edges c_nc₁ and d_nd₁ are substituted with c_nd₁ and d_nc₁ 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].

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.

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

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}) \cup E (B_{i}) \cup {d_{i - 1}^{″} c_{i}^{″}, d_{i - 1}^{'} c_{i}^{'}, b_{i - 1} b_{i}}$ .

This is described in Fig. 5.

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}^{″}}) \cup {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].

Fig. 6

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

Fig. 7

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

4 Main results

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) = {\begin{matrix} C_{1}, & u \in {b_{3 i - 2}, c_{3 i - 2}, d_{3 i - 2} : i \in [[\frac{n}{3}]]} \\ ∥ C_{2}, & u \in {b_{3 i - 1}, c_{3 i - 1}, d_{3 i - 1} : i \in [[\frac{n}{3}]]} \\ ∥ C_{3}, & u \in {b_{3 i}, c_{3 i}, d_{3 i} : i \in [[\frac{n}{3}]]} \\ ∥ C_{4}, & u \in {a_{i} : i \in [[n]]} \end{matrix}$

Case 2: n ≡ 1 (mod 3) $f (u) = C_{1}, u \in {b_{3 i - 2}, c_{3 i - 2}, d_{3 i - 2} : i \in [[\frac{n - 1}{3}]]}$ $f (u) = C_{2}, u \in {b_{3 i - 1}, c_{3 i - 1}, d_{3 i - 1} : i \in [[\frac{n - 1}{3}]]} \cup {b_{n}, c_{n}, d_{n}}$ , $f (u) = C_{3}, u \in {b_{3 i}, c_{3 i}, d_{3 i} : i \in [[\frac{n - 1}{3}]]}$ , $f (u) = C_{4}, u \in {a_{i} : i \in [[n]]}$ .

Case 3: n ≡ 2 (mod 3) For n = 5, $f (u) = C_{1} : u \in {b_{1}, c_{1}, d_{1}, b_{3}, c_{3}, d_{3}}$ , $f (u) = C_{2} : u \in {b_{2}, c_{2}, d_{2}, a_{4}, a_{5}}$ , $f (u) = C_{3}, u \in {a_{1}, a_{2}, b_{4}, c_{4}, d_{4}}$ , $f (u) = C_{4}, u \in {a_{3}, b_{5}, c_{5}, d_{5}}$ .

See Fig. 8.

Fig. 8

Star coloring scheme of J₅.

Case 3.1: When n ≠ 5 $f (u) = {\begin{matrix} C_{1}, & u \in {b_{3 i - 2}, c_{3 i - 2}, d_{3 i - 2} : i \in [[\frac{n - 5}{3}]]} \cup {b_{n - 3}, c_{n - 3}, d_{n - 3}} \\ C_{2}, & u \in {b_{3 i - 1}, c_{3 i - 1}, d_{3 i - 1} : i \in [[\frac{n - 5}{3}]]} \cup {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 \in {b_{3 i}, c_{3 i}, d_{3 i} : i \in [[\frac{n - 5}{3}]]} \cup {b_{n - 1}, c_{n - 1}, d_{n - 1}} \\ C_{4}, & u \in {a_{i} : i \in [[n]]} \end{matrix}$

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) = {\begin{matrix} C_{1} : & u \in {a_{2}, b_{1}, d_{3}, c_{3}^{'}, d_{1}^{'}, d_{1}^{″}} \\ C_{2} : & u \in {a_{3}, b_{2}, d_{1}, c_{1}^{'}, d_{2}^{'}, d_{2}^{″}} \\ C_{3} : & u \in {a_{1}, b_{3}, d_{2}, c_{2}^{'}, d_{3}^{'}, d_{3}^{″}} \\ C_{4} : & u \in {c_{1}, c_{2}, c_{3}, c_{1}^{″}, c_{2}^{″}, c_{3}^{″}} \end{matrix}$

The edge set $E ({TG}_{3}) = (E (G_{3}) \ {c_{1}^{″} d_{3}^{″}, c_{1}^{'} d_{3}^{'}}) \cup {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.

Fig. 9

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

Case 2: For n = 5 $f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {a_{1}, c_{2}^{'}, c_{2}^{″}, c_{3}^{'}, c_{3}^{″}, b_{4}, c_{4}^{'}, c_{4}^{″}, d_{5}^{'}, d_{5}^{″}} \\ C_{3}, & u \in {b_{1}, c_{1}^{'}, c_{1}^{″}, a_{2}, c_{3}, d_{3}, d_{4}^{'}, d_{4}^{″}, c_{5}, d_{5}} \\ C_{4}, & u \in {c_{1}, d_{1}, b_{2}, d_{2}^{'}, d_{2}^{″}, a_{3}, c_{4}, d_{4}, a_{5}} \end{matrix}$

The edge set $E ({TG}_{5}) = (E (G_{5}) \ {c_{1}^{'} d_{5}^{'}, c_{1}^{″} d_{5}^{″}}) \cup {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.

Fig. 10

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

Fig. 11

Bicolor partition of G₅.

Case 3: For n ≥ 7

Case 3.1: n = 4t + 3, t = 1, 2, 3… For $i \in [[\frac{n + 1}{4}]]$ , $f (u) = {\begin{matrix} C_{1}, & u \in {b_{4 i - 3}, d_{4 i - 3}^{'}, d_{4 i - 3}^{″}, a_{4 i - 2}} \\ C_{2}, & u \in {d_{4 i - 3}, c_{4 i - 3}^{'}, b_{4 i - 2}, d_{4 i - 2}^{'}, d_{4 i - 2}^{″}} \\ C_{3}, & u \in {c_{4 i - 3}, c_{4 i - 3}^{″}, c_{4 i - 2}^{'}, d_{4 i - 2}} \\ C_{4}, & u \in {a_{4 i - 3}, c_{4 i - 2}, c_{4 i - 2}^{″}} \end{matrix}$

For $i \in [[\frac{n - 3}{4}]]$ , $f (u) = {\begin{matrix} C_{1}, & u \in {c_{4 i - 1}, c_{4 i - 1}^{″}, d_{4 i}, c_{4 i}^{'}} \\ C_{2}, & u \in {a_{4 i - 1}, c_{4 i}, c_{4 i}^{″}} \\ C_{3}, & u \in {b_{4 i - 1}, d_{4 i - 1}^{'}, d_{4 i - 1}^{″}, a_{4 i}} \\ C_{4}, & u \in {d_{4 i - 1}, c_{4 i - 1}^{'}, b_{4 i}, d_{4 i}^{'}, d_{4 i}^{″}} \end{matrix}$

$f (u) = {\begin{matrix} C_{1}, & u \in {d_{n}, c_{n}^{'}} \\ C_{2}, & u \in {c_{n}} \\ C_{3}, & u \in {a_{n}, c_{n}^{″}} \\ C_{4}, & u \in {b_{n}, d_{n}^{'}, d_{n}^{″}} \end{matrix}$

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

Case 3.2.1: n ≡ 0 (mod 3) For $i \in [[\frac{n}{3}]]$ , $f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {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 \in {a_{3 i - 2},, b_{3 i}, c_{3 i - 1}^{'}, d_{3 i - 1}, d_{3 i}^{'}, d_{3 i}^{″}} \\ C_{4}, & u \in {c_{3 i - 2}^{″}, c_{3 i - 2}, c_{3 i - 1}^{″}, c_{3 i - 1}, c_{3 i}^{″}, c_{3 i}} \end{matrix}$

Case 3.2.2: nnotequiv0 (mod 3). For $i \in [[\frac{n - 9}{4}]]$

$f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {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 \in {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 \in {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}^{″}} \end{matrix}$

$f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {d_{n - 8}, c_{n - 8}^{'}, d_{n - 5}, c_{n - 5}^{'}, d_{n - 2}, c_{n - 2}^{'}} \\ C_{3}, & u \in {c_{n - 8}, c_{n - 8}^{″}, c_{n - 5}, c_{n - 5}^{″}, c_{n - 2}, c_{n - 2}^{″}} \\ C_{4}, & u \in {a_{n - 8}, a_{n - 5}, a_{n - 2}} \end{matrix}$

$f (u) = {\begin{matrix} C_{1}, & u \in {a_{n - 7}, a_{n - 4}, a_{n - 1}} \\ ∥ C_{2}, & u \in {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 \in {c_{n - 7}^{'}, d_{n - 7}, c_{n - 4}^{'}, c_{n - 1}^{'}, d_{n - 4}, d_{n - 1}} \\ ∥ C_{4}, & u \in {c_{n - 7}, c_{n - 7}^{″}, c_{n - 4}, c_{n - 4}^{″}, c_{n - 1}, c_{n - 1}^{″}} \end{matrix}$

$f (u) = {\begin{matrix} C_{1}, & u \in {d_{n - 6}, c_{n - 6}^{'}, d_{n - 3}, c_{n - 3}^{'}, d_{n}, c_{n}^{'}} \\ ∥ C_{2}, & u \in {c_{n - 6}, c_{n - 3}, c_{n}} \\ ∥ C_{3}, & u \in {a_{n - 6}, c_{n - 6}^{″}, a_{n - 3}, c_{n - 3}^{″}, a_{n}, c_{n}^{″}} \\ ∥ C_{4}, & u \in {b_{n - 6}, d_{n - 6}^{'}, d_{n - 6}^{″}, b_{n - 3}, d_{n - 3}^{'}, d_{n - 3}^{″}, b_{n}, d_{n}^{'}, d_{n}^{″}} \end{matrix}$

Since, $E ({TG}_{n}) = (E (G_{n}) \ {c_{n}^{'} d_{1}^{'}, c_{n}^{″} d_{1}^{″}}) \cup {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 \in [[\frac{n}{4}]]$ ,

$f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {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 \in {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 \in {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}^{″}} \end{matrix}$

Case 2: nnotequiv0 (mod 4)

Case 2.1: n ≡ 0 (mod 3) For $i \in [[\frac{n}{3}]]$ , $f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {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 \in {a_{3 i - 2}, b_{3 i}, c_{3 i - 1}^{'}, d_{3 i - 1}, d_{3 i}^{'}, d_{3 i}^{″}} \\ ∥ C_{4}, & u \in {c_{3 i - 2}, c_{3 i - 1}, c_{3 i}, c_{3 i - 2}^{″}, c_{3 i - 1}^{″}, c_{3 i}^{″}} \end{matrix}$

Case 2.2: nnotequiv0 (mod 3) For $i \in [[\frac{n - 6}{4}]]$ , $f (u) = {\begin{matrix} C_{1}, & u \in {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 \in {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 \in {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 \in {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}^{″}} \end{matrix}$

$f (u) = {\begin{matrix} C_{1}, & u \in {b_{n - 5}, d_{n - 5}^{'}, d_{n - 5}^{″}, b_{n - 2}, d_{n - 2}^{'}, d_{n - 2}^{″}} \\ ∥ C_{2}, & u \in {d_{n - 5}, c_{n - 5}^{'}, d_{n - 2}, c_{n - 2}^{'}} \\ ∥ C_{3}, & u \in {c_{n - 5}, c_{n - 5}^{″}, c_{n - 2}, c_{n - 2}^{″}} \\ ∥ C_{4}, & u \in {a_{n - 5}, a_{n - 2}} \end{matrix}$ $f (u) = {\begin{matrix} C_{1}, & u \in {a_{n - 4}, a_{n - 1}} \\ ∥ C_{2}, & u \in {b_{n - 4}, d_{n - 4}^{'}, d_{n - 4}^{″}, b_{n - 1}, d_{n - 1}^{'}, d_{n - 1}^{″}} \\ ∥ C_{3}, & u \in {c_{n - 4}^{'}, d_{n - 4}, c_{n - 1}^{'}, d_{n - 1}} \\ ∥ C_{4}, & u \in {c_{n - 4}, c_{n - 4}^{″}, c_{n - 1}, c_{n - 1}^{″}} \end{matrix}$ $f (u) = {\begin{matrix} C_{1}, & u \in {d_{n - 3}, c_{n - 3}^{'}, d_{n}, c_{n}^{'}} \\ ∥ C_{2}, & u \in {c_{n - 3}, c_{n}} \\ ∥ C_{3}, & u \in {a_{n - 3}, c_{n - 3}^{″}, a_{n}, c_{n}^{″}} \\ ∥ C_{4}, & u \in {b_{n - 3}, d_{n - 3}^{'}, d_{n - 3}^{″}, b_{n}, d_{n}^{'}, d_{n}^{″}} \end{matrix}$

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}^{″}}) \cup {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.

5 Conclusion

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.

References

Grünbaum

, Acyclic colorings of planar graphs, Israel Journal of Mathematics 14(4) (1973), 390–408.

Fertin

, Raspaud

and Reed

, Star coloring of graphs, Journal of Graph Theory 47(3) (2004), 163–182.

Albertson

M.O.

, Chappell

G.G.

, Kierstead

H.A.

, Kündgen

and Ramamurthi

Coloring with no 2-colored P₄’s, The Electronic Journal of Combinatorics 11(1) (2004), R26–R26.

Vince

Star chromatic number, Journal of Graph Theory 12(4) (1988), 551–559.

Kierstead

H.A.

, Kündgen

and Timmons

Star coloring bipartite planar graphs, Journal of Graph Theory 60(1) (2009), 1–10.

Coleman

T.F.

and Moré

J.J.

Estimation of sparse Hessian matrices and graph coloring problems, Mathematical Programming 28 (1984), 243–270.

, Cranston

D.W.

, Montassier

, Raspaud

and Wang

Star coloring of sparse graphs, Journal of Graph Theory 62(3) (2009), 201–219.

Lyons

, Acyclic and star colorings of cographs,, Discrete Applied Mathematics 159(16) (2011), 1842–1850.

Karthick

and Subramanian

C.R.

, Star coloring of subcubic graphs, Discussiones Mathematicae Graph Theory 33(2) (2013), 373–385.

10.

Karthick

, Star coloring of certain graph classes, Graphs and Combinatorics 34 (2018), 109–128.

11.

Akbari

, Chavooshi

, Ghanbari

and Taghian

, Star coloring of the Cartesian product of cycles, arXiv preprint arXiv:1906.06561, (2019).

12.

Shalu

M.A.

and Antony

, Star colouring of bounded degree graphs and regular graphs, Discrete Mathematics 345(6) (2022), 112850.

13.

Ramamurthi

and Sanders

, Star coloring outerplanar bipartite graphs, Discussiones Mathematicae Graph Theory 39(4) (2019), 899–908.

14.

Shalu

M.A.

and Sandhya

T.P.

, Star coloring of graphs with girth at least five, Graphs and Combinatorics 32 (2016), 2121–2134.

15.

Kündgen

and Timmons

Star coloring planar graphs from small lists, Journal of Graph Theory 63(4) (2010), 324–337.

16.

Zhou

, Some theorems concerning the star chromatic number of a graph, Journal of Combinatorial Theory Series B 70(2) (1997), 245–258.

17.

Steffen

and Zhu

Star chromatic numbers of graphs,, Combinatorica 16 (1996), 439–448.

18.

Guichard

D.R.

Acyclic graph coloring and the complexity of the star chromatic number, Journal of Graph Theory 17(2) (1993), 129–134.

19.

Cary

Dominator chromatic numbers of orientations of trees, Open Journal of Discrete Applied Mathematics 4(1) (2021), 4–11.

20.

Mphako-Banda

and Kok

Stability in respect of chromatic completion of graphs, Open Journal of Discrete Applied Mathematics 5(2) (2022), 11–18.

21.

Kok

Introduction to total chromatic vertex stress of graphs, Open Journal of Discrete Applied Mathematics 6(2) (2023), 32–38.

22.

Gebremedhin

A.H.

, Tarafdar

, Pothen

and Walther

Efficient computation of sparse Hessians using coloring and automatic differentiation, Informs Journal on Computing 21(2) (2009), 209–223.

23.

Gebremedhin

A.H.

, Tarafdar

, Manne

and Pothen

New acyclic and star coloring algorithms with application to computing Hessians, SIAM Journal on Scientific Computing 29(3) (2007), 1042–1072.

24.

Cameron

P.J.

, Chetwynd

A.G.

and Watkins

J.J.

Decomposition of snarks, Journal of Graph Theory 11(1) (1987), 13–19.

25.

Kochol

, Snarks without small cycles, Journal of Combinatorial Theory Series B 67(1) (1996), 34–47.

26.

Steffen

andClassifications and characterizations of snarks, Discrete Mathematics 188(1-3) (1998), 183–203.

27.

Cavicchioli

, Murgolo

T.E.

, Ruini

and Spaggiari

, Special classes of snarks, Acta Applicandae Mathematicae 76(1) (2003), 57–88.

28.

Ghebleh

, Norine

and Thomas

The circular chromatic index of flower snarks, The Electronic Journal of Combinatorics (2006), N20.

29.

Campos

C.N.

, Dantas

and de Mello

C.P.

The total-chromatic number of some families of snarks, Discrete Mathematics 311(12) (2011), 984–988.

30.

da Soledade Gonzaga

L.G.

and de Almeida

S.M.

, Sigma coloring on powers of paths and some families of snarks, Electronic Notes in Theoretical Computer Science 346 (2019), 485–496.

31.

Brinkmann

and Goedgebeur

, Generation of cubic graphs and snarks with large girth, Journal of Graph Theory 86(2) (2017), 255–272.

32.

Brinkmann

, Preissmann

and Sasaki

Snarks with total chromatic number 5, Discrete Mathematics and Theoretical Computer Science 17(1) (2015), 369–382.

33.

Palma

M.A.

, Gonçalves

I. F

, Sasaki

and Dantas

, On total coloring and equitable total coloring of infinite snark families, RAIRO-Operations Research 57(5) (2023), 2619–2637.

34.

Zhan

J.M.

, Wang

J. J.

, Ding

W. P.

and Yao

Y. Y.

, Three-way behavioral decision making with hesitant fuzzy information systems: Survey and challenges, IEEE/CAA Journal of Automatica Sinica 10(2) (2023), 330–350.

35.

Fernández-Alemán

J.L.

, Señor

I.C.

, Lozoya

P.Á.O.

and Toval

Security and privacy in electronic health records: A systematic literature review, Journal of Biomedical Informatics 46(3) (2013), 541–562.

36.

Mahapatra

, Ghorai

and Pal

Fuzzy fractional coloring of fuzzy graph with its application, Journal of Ambient Intelligence and Humanized Computing 11 (2020), 5771–5784.

37.

Isaacs

, Infinite families of nontrivial trivalent graphs which are not Tait colorable, The American Mathematical Monthly 82(3) (1975), 221–239.

38.

Wenping

, Xiaohui

, Yuansheng

and Xiwu

, The crossing number of flower snarks and related graphs, Ars Combinatoria 86 (2008), 57–64.

39.

Mila

, Stafford

C.A.

and Capponi

, Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons, Physical Review B 57(3) (1998), 1457–1460.

40.

Grötschel

, Jünger

and Reinelt

, On the acyclic subgraph polytope, Mathematical Programming 33 (1985), 28–42.

41.

Walba

, Richards

and Haltiwanger

R.C.

Total synthesis of the first molecular Möbius strip, Journal of the American Chemical Society 104(11), 3219–3221.

42.

Flapan

, Symmetries of Möbius ladders, Mathematische Annalen 283(2) (1989), 271–283.

43.

Goldberg

M.K.

, Construction of class 2 graphs with maximum vertex degree 3, Journal of Combinatorial Theory Series B 31(3) (1981), 282–291.

44.

Zhang

, Wang

and Zhang

Feedback numbers of Goldberg snark, twisted Goldberg snarks and related graphs, In ITM Web of Conferences EDP Sciences 25 (2019), 01012.

45.

Xie

, Xiao

and Zhao

, Star coloring of cubic graphs, Information Processing Letters 114(12) (2014), 689–691.