Further results on equitable near proper coloring of derived graph families

Sabitha Jose1, Sudev Naduvath1
1Department of Mathematics Christ University, Bangalore, India

Abstract

A proper coloring assigns distinct colors to the adjacent vertices of a graph. An equitable near proper coloring of a graph G is an improper coloring in which neighbouring vertices are allowed to receive the same color such that the cardinalities of two distinct color classes differ by not more than one and the number of monochromatic edges is minimised by giving certain restrictions on the number of color classes that can have an edge between them. This paper discusses the equitable near proper coloring of line, middle, and total graphs of certain graph classes, such as paths, cycles, sunlet graphs, star graphs, and gear graphs.

Keywords: Equitable near proper coloring, Line graph, Middle graph, Total graph

1. Introduction

All graphs considered in this paper are finite, connected, simple, and undirected. For basic terminologies and notations, we refer to [1,10].

Graph coloring is an extensively studied area in graph theory. A proper vertex coloring is an assignment of colors to the vertices of the graph in which neighbouring vertices receive distinct colors. Equitable coloring of graphs was introduced in 1973 (see [9]) and defined as a proper vertex coloring in which the cardinalities of the color classes differ by not more than 1. The least integer value k for which G is equitably k colorable is known as the equitable chromatic number denoted by χe(G).

An improper coloring or a defective coloring of G allows the adjacent vertices to receive the same colors. The resulting monochromatic edges are also called bad edges. A near proper coloring of G is a defective coloring in which the number of bad edges is minimised by restricting the adjacency of elements within the color classes [8]. A defective coloring problem arises when there is a situation that does not have enough resources. When there are insufficient resources to color a graph, near proper coloring plays an essential role in the literature. Motivated by the above studies, the notion of equitable near proper coloring is introduced in [2] and stated as follows.

Definition 1.1.

[2] An equitable near proper coloring (or ENP k-coloring) of a graph G is a defective coloring in which the set of vertices of G can be partitioned into k color classes V1,V2,,Vk such that ||Vi||Vj||1 for any 1ijk and the number of bad edges is minimised by restricting the number of color classes that can have adjacency among their elements.

Definition 1.2.

 The minimum number of monochromatic edges or bad edges resulting from an ENP k-coloring of G is defined as equitable defective number and is denoted by bχek(G).

In an ENP coloring, the vertex set is partitioned into k color classes by the integer partitioning of n, the order of the graph such that n=a1+a2++ak where |aiaj|1; 1ijk and ai is the cardinality of the i-th color class Vi of G. When the available number of colors increases, the cardinality of each color class decreases to maintain the equitability constraint. The colors can be suitably assigned to the vertices in such a manner that the number of resulting monochromatic edges is minimum. This coloring technique is used for all graph classes under consideration to get the minimum possible number of monochromatic edges in all cases. Integer partitioning technique is used as the fundamental method in the study to suitably identifying the optimal coloring schema. To ensure the optimality, the equitable integer partitioning technique is followed to decide the cardinality of color classes.

Graphs with equitable chromatic number 2 are excluded from this discussion, as coloring a graph with only one color makes all edges monochromatic. Hence, we consider the cases when χe(G)3.

Throughout the discussion, {c1,c2,,ck} be the k available colors, and {V1,V2,,Vk} are the corresponding color classes. In an ENP-coloring, all possible values for k where 2kχe(G)1 are considered. The function c(vi) represents the color assigned to the vertex vi. The monochromatic edges resulting from an ENP k-coloring are represented by dotted lines.

ENP coloring offers a broad scope of research. The studies in this direction can be viewed in [4,3,5].

2. ENP k-coloring of line graph, middle graph and total graph

Let G be a graph with vertex set V(G) and edge set E(G). The line graph of G, denoted by L(G), is the graph whose vertex set is the edge set of G with two vertices of L(G) that are adjacent whenever the corresponding edges of G are adjacent.

The middle graph of G, denoted by M(G), is the graph whose vertex set is V(G)E(G), where two vertices in M(G) are adjacent if and only if they are either adjacent edges of G or one is a vertex and the other is an edge incident with it.

The total graph of G, denoted by T(G), has vertex set V(G)E(G), and the edges join all elements of this vertex set that are adjacent or incident in G.

This paper discusses the ENP k-coloring of the line, middle, and total graph of paths, cycles, sunlet graphs, star graphs, and gear graphs and also investigates the corresponding equitable defective number. Throughout the discussion, let {c1,c2,,ck} be the available colors and {V1,V2,,Vk} be the corresponding color classes. In an ENP k-coloring, we consider all possible cases for k where 1<k<χe(G). The bad edges resulting from an ENP k-coloring are represented by dotted lines.

2.1. ENP k-coloring of path graph families

The line graph of a path graph of order n is a path graph of order n1, and hence the equitable chromatic number is 2. In an ENP k-coloring, we consider only the graphs with χe(G)3, and thus the line graph of paths is omitted from our study.

The equitable coloring of the middle graph of a path contains three colors. The following theorem describes the ENP k-coloring of the middle graph of a path graph.

Theorem 2.1. For a path Pn where n3, bχe2(M(Pn))=n2.

Proof. Consider V(Pn)={v1,v2,,vn} and E(Pn)={e1,e2,,en1}. Then, V((M(Pn))=V(Pn)E(Pn). Thus, M(Pn) contains 2n1 vertices, and observe that χe(M(Pn))=3. In an ENP k-coloring, only one case k=2 is to be considered.

It is possible to partition the vertex set into two subsets, V1={v1,v2,,vn} and V2={e1,e2,,en1}. Now, assign the vertices in V1 with the color c1 and V2 with the color c2. Since ei ; 1in1 forms a path of order n2, bχek(M(Pn))=n2, as n2 monochromatic edges are formed among the vertices ei.

Another possible way of an ENP k-coloring is defined as follows: c(vi)={c1,if i1,2mod4;c2,if i0,3mod4.

This coloring results in n2 monochromatic edges of the form viei ; 1in1 or eivj ; 1in1 , 1jn. It also yields in n2 monochromatic edges, and thus bχek(M(Pn))=n2◻

Figure 1 depicts an ENP 2-coloring of the middle graph of paths.

Figure 1 M P4) with ENP 2-coloring

The total graph of a path contains 2n1 vertices and χe(T(Pn))=3. The succeeding theorem addresses the ENP k-coloring of the total graph of paths when k=2.

Theorem 2.2.

For a path Pn where n3, bχe2(T(Pn))=n1.

Proof. Let V((T(Pn))={v1,v2,,vn,e1,e2,,en1}, and in an ENP k-coloring, the below situations are investigated.

Case 1: When n is even, we partition the vertex set V(T(Pn)) as follows:

V1={v1,e1,v3,e3,,vn1en1} and V2={v2,e2,v4,e4,,vn2,en2,vn}.

Case 2: When n is odd, V(T(Pn)) is partitioned as below:

V1={v1,e1,v3,e3,,vn2en2,vn} and V2={v2,e2,v4,e4,,vn1,en1}.

In both cases, it is evident that ||V1||V2||=1. Now, assigning the vertices of V1 with the color c1 and V2 with the color c2, we observe that every edge viei ; 1in1 is a monochromatic edge, and hence the equitable defective number is n1◻

Figure 2 depicts an ENP 2-coloring of the total graph of paths.

Figure 2 . T (P5) with ENP 2-coloring

2.2. ENP k-coloring of cycle graph families

The line graph of a cycle Cn is the cycle Cn itself. Hence, the equitable chromatic number is 2 when n is even and 3 when n is odd. When k=2 and n is odd, the equitable defective number is 1.

The subsequent theorem examines the ENP k-coloring of the middle graph of cycles for k=2.

Theorem 2.3.

For a cycle Cn, bχek(M(Cn))=n.

Proof. Let V(Cn)={v1,v2,,vn} and E(Cn)={e1,e2,,en}. Now,
V(M(Cn))=V(Cn)E(Cn), and note that χe(M(Cn))=3, and thus the ENP k-coloring considers only one case k=2. In the first possible ENP k-coloring, assign all of the vertices vi and ei with the colors c1 and c2 respectively, and it can be observed that every edge between the vertices ei is a monochromatic edge, and thus the equitable defective number is n.

The second possible ENP k-coloring may be performed as in Theorem 2.1, and this coloring also produces n monochromatic edges. Additionally, there are n monochromatic edges of the form viei ; 1in for even n; however, for odd n, there are n1 monochromatic edges of the form viei ; 1in1 and one en1en monochromatic edge. Thus, bχe2(M(Cn))=n◻

Figure 3 depicts an ENP 2-coloring of the middle graph of cycles.

Figure 3 An ENP 2-coloring of middle graph of cycles

The following theorem describes the ENP k-coloring of the total graph T(Cn) of a cycle.

Theorem 2.4.

For T(Cn) where n3, bχek(T(Cn))={n;if k=2, n is even,n+1;if k=2, n is odd,1;if k=3.

Proof. Note that χe(T(Cn))=3 when n0mod3 and 4 otherwise. Hence, the following cases need to be addressed here.

Case 1: Assume that k=2 and n is even. We partition the vertex set so that V1={v1,e1,v3,e3,vn1,en1} and V2={v2,e2,v4,e4,vn,en}. Now, |V1|=|V2|, and every viei edge, where 1in, is a monochromatic edge. Thus, the equitable defective number is n.

Case 2: Assume that k=2 and n is odd. Let us partition the vertex set such that V1={v1,e1,v3,e3,vn2,en2,vn} and V2={v2,e2,v4,e4,vn1,en1,en}. Here, |V1|=|V2| and n1 monochromatic edges are obtained connecting vi and ei ; 1in1. Furthermore, another v1vn and en1en monochromatic edges are obtained. Thus, the equitable defective number, in this case, is n+1 (see Figure 4 for illustration).

Case 3: When k=3 and n0mod3, assign the vertices with the three available colors in a cyclic order by considering the equitability condition. Here, the equitable defective number is 1◻

Figure 4 depicts an ENP 2-coloring of the total graph of cycles.

Figure 4 An ENP 2-coloring of total graph of cycles

2.3. ENP k-coloring of sunlet graph families

A sunlet graph denoted by Sln is obtained by attaching n pendant edges to a cycle Cn. ENP k-coloring of sunlet graphs is discussed in [4]. In a sunlet graph, the vertices corresponding to Cn are termed as rim vertices.

The following theorem investigates the ENP k-coloring of the line graph of a sunlet graph.

Theorem 2.5.

The equitable defective number of L(Sln), where n3, is n.

Proof. Consider V(L(Sln))={v1,v2,,vn,u1,u2,,un}, where vi induces a cycle of order n, and ui are the vertices that are adjacent with both vi and vi+1. The equitable coloring of L(Sln) contains 3 colors (see [7]), and thus, in an ENP k-coloring, only one case as k=2 is considered. Let c1 and c2 be the two available colors, and the following cases need to be considered.

Case 1: Let n be even. Then, the vi ; 1in vertices can be properly colored with the two available colors. When the remaining vertices are assigned the same colors equitably, n monochromatic edges are obtained between vi and ui ; 1in.

Case 2: Let n be odd and follow the same coloring procedure as in Case 1. That is, assign v1 with the color c1, v2 with the color c2, and so on. Since n is odd, both v1 and vn receive the same color, and thus there is a v1vn monochromatic edge on the rim. Now, the vertex adjacent to both v1 and vn receives an alternate color from the color assigned to both of them. Further, the remaining vertices can be assigned in an equitable manner. Thus, n1 monochromatic edges are obtained between the vertices vi and ui, and the equitable defective number is n.

Combining the above two cases, bχe2(L(Sln))=n◻

An ENP 2-coloring of the line graph of sunlet graphs is illustrated in Figure 5.

Figure 5 An ENP 2-coloring of sunlet graphs

An ENP k-coloring of the middle graph of a sunlet graph for distinct values of n is discussed in the next theorem.

Theorem 2.6. For a sunlet graph Sln, where n3, bχek(M(Sln))={2n;if k=2,n;if k=3.

Proof. Consider V(M(Sln))={v1,v2,,vn,u1,u2,,un,v1,v2,,vn,u1,u2,,un}. Here, the vertices v1,u1,v2,u2,,vn,un forms an inner 2n – cycle termed as the rim vertices of M(Sln), and each vi; 1in is connected to the corresponding vi; 1in forms an outer n – cycle. Again, ui; 1in are the pendant vertices connected to the corresponding vi. Recall that χe(M(Sln))=4 (see [7]), and in an ENP k-coloring, two cases are to be considered as k=2 and k=3.

Case 1: Assume k=2 and we partition the vertex set as follows.

V1={u1,u2,,un,u1,u2,,un} and V2={v1,v2,,vn,v1,v2,,vn}. Assign the vertices in V1 with the color c1 and V2 with the color c2. Now, |V1|=|V2|, and n monochromatic edges generated among the vertices ui. Additionally, the vertices vi and vi have n monochromatic edges connecting them, where 1in. Thus, the equitable defective number is 2n.

Case 2: Let k=3. Among the 4n vertices of M(Sln), 2n vertices are on the rim. Assign all the rim vertices with the three available colors, say c1, c2, and c3, in a cyclic order, and consider the following three subcases.

Subcase 2.1: When n0mod3, 2n0mod3, and assign the rim vertices with the three colors in a cyclic order such that each color repeats exactly 2n3 times without creating any monochromatic edges. Now, assign the vertices vi with the same color received by the vertices vi, and n monochromatic edges are obtained in between the vertices vi and vi ; 1in. Further, the vertices ui can be equitably assigned these three colors without creating monochromatic edges. Thus, there are n monochromatic edges.

Subcase 2.2: When n1mod3, 2n2mod3, follow the same coloring procedure for the rim vertices vi and ui where 1in creates a u1un monochromatic edge. Since 2n2mod3, to attain the equitability, color c3 can be assigned to v1. The remaining vi; (2in) can receive the same color received by vi to obtain n1 monochromatic edges of the form vivi (2in). Further, each ui; (1in) can be received any of the three colors equitably with the condition that vi and the corresponding ui receive different colors leading to the equitable defective number as n.

Subcase 2.3: When n2mod3, 2n1mod3, and the rim vertices follow the same coloring pattern as in the previous subcases leads to a v1un monochromatic edge. Further, the remaining vertices vi and ui can receive any of the three colors by considering the equitability condition, creates n1 monochromatic edges as in Subcase 2.2. Hence, the equitable defective number in this case is n.

Thus, combining the above three subcases, bχe3(M(Sln))=n◻

An ENP 2-coloring of the middle graph of the sunlet graphs is illustrated in Figure 6.

Figure 6 An ENP 2-coloring of middle graph of sunlet graphs

The following theorem discusses the ENP k-coloring of the total graph of sunlet graphs for different parities of n and for k=2,3.

Theorem 2.7.

For T(Sln) where n3, bχek(T(Sln))={3n;if k=2,n;if k=3,n0,2mod3,n+1;if k=3,n1mod3.

Proof. Consider the vertex sets and the adjacencies as in Theorem 2.6. Observe that χe(T(Sln))=4 (see [7]); thus, in an ENP k-coloring, the following cases need to be considered.

Case 1: When k=2, repeat the same coloring procedure as in Case-1 of Theorem 2.6, and we obtain the equitable defective number as 3n.

Case 2: When k=3, follow the same coloring pattern as in Case-2 of Theorem 2.6 by considering the equitability condition and maximising the properness of the coloring, there are the following observations.

Subcase 2.1: When n0modk, n monochromatic edges are obtained of the form vivi ; 1in as in Theorem 2.6.

Subcase 2.2: When n1modk, two monochromatic edges are obtained, one among the vertices vi and one among the vertices ui. Apart from that, the vertices vi and vi ; 2in1 have n1 monochromatic edges connecting them. Thus, the equitable defective number is n+1. (See Figure ??? for reference.)

Subcase 2.3: When n2modk, we get the same n1 monochromatic edges as in Subcase 2.2 and an additional monochromatic edge v1un. Thus, the equitable defective number is n. (refer to Figure 7 for illustration.) ◻

An ENP 3-coloring of the total graph of sunlet graphs is illustrated in Figure 7.

Figure 7 An ENP 3-coloring of total graph of sunlet graphs

2.4. ENP k-coloring of star graph families

The line graph of a star graph K1,n is a complete graph of order n. The ENP k-coloring and the corresponding equitable defective number of complete graphs are discussed in [2] and as follows.

Theorem 2.8 [2] For a complete graph Kn, the equitable defective number is given by bχek(Kn)=12{rnknk1+(kr)nknk1}; where nrmodk and r is the number of color classes with maximum cardinality.

The following theorem describes the ENP k-coloring of the middle graph of star graphs.

Theorem 2.9. For M(K1,n), bχek(M(K1,n))={bχek(Kn+1);if k2; kn,1;if k=n.

Proof. Consider V(K1,n)={v,v1,v2,,vn} and E(K1,n)={e1,e2,,en}. Consider u1,u2,,un as the corresponding vertex set of E(K1,n). These edges form a clique of order n in M(K1,n), and hence χe(M(K1,n))=n+1 as the vertices v,u1,u2,,un induce a complete graph of order n+1. Thus, in an ENP k-coloring, 2kn and the following cases need to be considered.

Case 1: When k2 and kn, assign the k available colors, say c1,c2,,ck alternately to the vertices ui ; 1in. Now, color the vi vertices so that each ui and the corresponding vi receive different colors in an equitable manner. Also, assign the vertex v with any available colors such that v receives the least used color assigned to the vertices ui. Since, {v,u1,u2,,un} induces a clique of order n+1, the equitable defective number in this case is bχek(Kn+1).

Case 2: When k=n, assign the vertices ui using the k colors, and the corresponding vertices vi can be assigned using the same colors such that both ui and the corresponding vi receive different colors, and as a result of this assignment no monochromatic edges obtained. Further, assign the vertex v with any available colors; only one vui monochromatic edge is obtained, and thus the equitable defective number is 1◻

Figure 8 depicts an ENP 2-coloring of the middle graph of star graphs.

Figure 8 An ENP 2-coloring of middle graph of star graphs

The subsequent theorem determines the equitable defective number of the total graph of star graphs for distinct values of n and for various values of k.

Theorem 2.10.

For the total graph T(K1,n) of a star graph where n3, bχek(T(K1,n))={bχek(Kn)+n;if k=2,bχek(Kn)+2n+1k1;if k3; kn,2;if k=n.

Proof. Consider the vertices as in Theorem 2.9. Note that χe(T(K1,n))=n+1 as {v,u1,u2,,un} induces a clique of order n+1. The vertices u1,u2,,un induce a clique of order n, and let v1,v2,,vn be the vertices that are adjacent to u1,u2,,un, respectively. In T(K1,n), the vertex v is adjacent to all the vertices ui and vi (1in). The ENP k-coloring of complete graphs is discussed in Theorem 2.8. Hence, the following cases need to be addressed here.

Case 1: When k=2, assign the two available colors, say c1 and c2, for every alternate vertex of the complete graph. Further, if c(ui)=c1 (or c2), then assign c(vi)=c2 (or c1). Now, c(v)=c1 or c2, and based on this assignment, the following observations are to be noted.

When n is even, n2 monochromatic edges of the form vui and n2 monochromatic edges of the form vvi are obtained. When n is odd, we get n2 monochromatic edges of the form vui and n2 monochromatic edges of the form vvi. Consequently, in both cases, the equitable defective number is bχek(Kn)+n.

Case 2: When k3 and kn, we can assign all the vertices with the k available colors in an equitable manner as follows. When the vertex set is partitioned into k color classes, each color class consists of either 2n+1k vertices or 2n+1k vertices. If the vertex v is placed in the color class with minimum cardinality 2n+1k, we obtain 2n+1k1 monochromatic edges. Hence, together with the monochromatic edges from Kn, the equitable defective number is bχek(Kn)+2n+1k1.

Case 3: When k=n, we can properly color the complete graph of order n with the k available colors, and the vertices v1,v2,,vn can also be properly colored with these k colors. Further, assign the vertex v with any of the k available colors, from which we obtain two monochromatic edges. ◻

Figure 9 depicts the ENP 3-coloring of the total graph of star graphs.

Figure 9 An ENP 3-coloring of total graph of star graphs

2.5. ENP k-coloring of gear graph families

A gear graph G1,n, which is a bipartite wheel graph, is obtained from a wheel graph by inserting a vertex between the rim vertices. That is, a gear graph is formed by adding a vertex between each pair of adjacent vertices of the outer cycle.

The subsequent theorem examines the ENP k-coloring of the line graph of a gear graph for different parities of n.

Theorem 2.11.

For L(G1,n), bχek((L(G1,n))={bχek(Kn)+n;if k=2,bχek(Kn);if k3.

Proof. Let V(G1,n)={v,v1,v2,,v2n} and E(G1,n)={e1,e2,,en,e1,e2,e2n} such that ei=vv2i1 ; 1in, ei=vivi+1 ; 1i2n1, and e2n=v2nv1. Consequently, V(L(G1,n))={e1,e2,,en,e1,e2,e2n}. Since ei ; 1in form a clique of order n in L(G1,n), χe(L(G1,n))=n. Subsequently, in an ENP k-coloring, consider 2kn1 and address the following cases.

Case 1: Assume k=2 and assign the vertices ei with the two available colors, say c1 and c2 alternately. This assignment yields the same amount of monochromatic edges as in the equitable defective number of a complete graph, that is stated in Theorem 2.8. Further, assign the vertices ej with the same available colors in a cyclic order satisfying the equitability condition, and we obtain n monochromatic edges in between the vertices ei and ej ; 1i,jn. Thus, bχek(Kn)+n gives the equitable defective number in this case.

Case 2: When k3, assign the vertices ei with the k available colors, bχek(Kn) monochromatic edges are obtained. By the definition of L(G1,n), each ei is adjacent to two distinct vertices ej, which forms a K3 that can be colored properly using the three available colors such that each vertex of K3 receives different color. This assignment of colors does not create any additional monochromatic edges; therefore, the equitable defective number is bχek(Kn)◻

An ENP k-coloring of the line graph of gear graphs is illustrated in Figure 10.

Figure 10 An ENP k-coloring of line graph of gear graphs

For various parities of n and distinct values of k, the theorem below discusses the ENP k-coloring of the middle graph of gear graphs.

Theorem 2.12. For M(G1,n), bχek(M(G1,n))={bχek(Kn+1)+3n;if k=2,2; n is odd,; n is evenbχek(Kn+1)+n;if k=3,n0,1modk,bχek(Kn+1)+n+1;if k=3,n2modk,bχek(Kn+1);if k4.

Proof. Consider V(G1,n)={v,v1,v2,,v2n}. Let E(G1,n)={e1,e2,,e2n}{ei,e2,,en} such that ei=vivi+1 ; 1i2n1, e2n=v2nv1 and ei=vv2i1 ; 1in. Consequently, V(M(G1,n))={v,v1,v2,,v2n,e1,e2,,e2n,e1,e2,e3,,en}. It is evident that the edges vei ; 1in, along with the vertex v form a clique of order n+1, and thus χe(M(G1,n))=n+1 (see [6]). In an ENP k-coloring, consider 2kn and address the following cases.

Case 1: Let k=2 and consider the subcases as given below.

Subcase 1.1: When n is even, partition the vertex set into two subsets as follows.

Let V1={vi:1i2n3 ; i1mod4} {vj:2j2n2 ; j2mod4} {ek:1kn1 ; k1mod2} {el:3l2n1 ; l3mod4} {em:4m2n ; m0mod4}.

V2={vi:3i2n1 ; i3mod4} {vj:4j2n ; j0mod4} {ek:2kn ; k0mod2} {el:1l2n3 ; l1mod4} {em:2m2n2 ; m2mod4}.

Now, |V1|=|V2|=5n+12. Hence, the central vertex v can be placed into any one of the color classes, resulting in ||V1||V2||=1. Further, assign the vertices in the set V1 with the color c1 and V2 with the color c2. As a result of this assignment of colors, we obtain n monochromatic edges of the form eivj ; 1in and 1j2n1 ; j1mod2. Also, the vertices vi and ei have n1 monochromatic edges connecting them, of the form viei+1, where 2i2n2 ; i0mod2 and there is a monochromatic edge e1v2n. Further, n monochromatic edges are obtained in between the vertices ei of the form eiei+1, where 1i2n1 ; 1mod2. Furthermore, together with the monochromatic edges from the complete graph that is investigated in Theorem 2.8, the equitable defective number is bχek(Kn+1)+3n.

Subcase 1.2: When n is odd, let us partition the vertex set as follows.

Let V1={vi:1i2n1 ; i1mod4} {vj:2j2n ; j2mod4} {ek:1kn ; k1mod2} {el:3l2n3 ; l3mod4} {em:4m2n2 ; m0mod4}.

V2={v} {vi:3i2n3 ; i3mod4} {vj:4j2n2 ; j0mod4} {ek:2kn1 ; k0mod2} {el:1l2n1 ; l1mod4} {em:2m2n ; m2mod4}.

Assign the vertices in V1 with the color c1 and V2 with the color c2. Now, |V1|=|V2|=5n+12 and the vertices vi and ei have n1 monochromatic edges connecting them, of the form viei, where 2i2n2 ; i0mod2. Moreover, the vertices ei and vj have n monochromatic edges connecting them of the form eivj ; 1in and 1j2n1 ; j1mod2. Furthermore, a monochromatic edge e1e2n and n monochromatic edges among the vertices ei of the form eiei+1 are generated, where 1i2n1 ; i1mod2. Now, along with the monochromatic edges obtained in the ENP k-coloring of complete graphs, the equitable defective number is bχek(Kn+1)+3n.

Case 2: When k=3, the following subcases are to be addressed.

Subcase 2.1: Let n0mod3. Assign the 4n vertices on the outer rim (vi ; 1i2n and ei ; 1i2n) using the three available colors in a cyclic order. Further, color the inner rim vertices (ei ; 1in) in the same cyclic order using the three colors such that both e1 and e1 receive the same color. Then, assign v with any one of the three colors. It can be observed that along with the monochromatic edges obtained from the complete graph, the vertices ei and vi generate n monochromatic edges of the form eivj ; 1in and 1j2n ; j1mod2. Thus, the equitable defective number is bχek(Kn+1)+n (see Figure 11 for illustration).

Subcase 2.2: Let n1mod3. Repeat the same coloring procedure as in Subcase 2.1 for the outer rim vertices vi and ei where 1i2n, except for one vertex. Since 4n1mod3, the additional vertex on the outer rim can be assigned the color c2. Further, the inner rim vertices can also be assigned as in Subcase 2.1, and since n1mod3, the additional vertex on the inner rim can be received the color c3. Further, the vertex v can receive the color c1 to maintain the equitability constraint. Here, we obtain the same number of monochromatic edges as compared to Subcase 2.1, and the equitable defective number is bχek(Kn+1)+n.

Subcase 2.3: Let n2mod3. We follow the same coloring procedure as in Subcase 2.1 for the outer rim vertices, and the last two vertices of the outer rim receive the colors c1 and c2 respectively. Further, the inner rim vertices can also be assigned in the same cyclic order as in the above two subcases, and the last two inner rim vertices can be assigned the colors c1 and c3 respectively. Finally, the vertex v can receive the color c2 to maintain the equitability constraint. In comparison with Subcase 2.1, we get an additional monochromatic edge of the form eiej. Therefore, the equitable defective number is bχek(Kn+1)+n+1 (see Figure 11).

Case 3: When k4, the vertices vi ; 1i2n, ei ; 1i2n and ei ; 1in can be assigned properly using the k available colors. Now the vertex v can also be received any of the available colors equitably, the resulting monochromatic edges are only from the clique. Thus, the equitable defective number is bχek(Kn+1). ◻

Figure 11 represents the ENP k-coloring of the middle graph of gear graphs.

Figure 11 An ENP 3-coloring of middle graph of gear graphs

The subsequent theorem examines the ENP k-coloring of the total graph of gear graphs for different parities of n and various values of k.

Theorem 2.13.

For the total graph of a gear graph G1,n, bχek(T(G1,n))={bχek(Kn+1)+9n2;if k=2,n even,bχek(Kn+1)+9n+12;if k=2,n odd,bχek(Kn+1)+n+n3;if k=3,n0modkbχek(Kn+1)+n+n3+2;if k=3,n1,2mod3bχek(Kn+1);if k4.

Proof. Note that V(T(G1,n))=V(M(G1,n)) and χe(T(G1,n))=n+1 (see [6]). The following observations are made when the same coloring procedure is followed, as in Theorem 2.12.

Case 1: When k=2 and n is even, apart from the monochromatic edges obtained as in Subcase-1.1 of Theorem 2.12, n1 monochromatic edges are obtained of the form vivi+1, where 1i2n2 ; i0mod2 along with a monochromatic edge v1v2n. Further, there are n2 monochromatic edges connecting vi and v. Thus, the equitable defective number is bχek(Kn+1)+9n2.

Case 2: When k=2 and n is odd, along with the monochromatic edges obtained as in Subcase-1.2 of Theorem 2.12, we may obtain n monochromatic edges of the form vivi+1, where 2i2n2 ; i0mod2 and another monochromatic edge v1v2n also obtained. Further, there are n2 monochromatic edges connecting the vertices vi and v. Hence, the equitable defective number is bχek(Kn+1)+9n+12.

Case 3: When k=3, we have the below observations.

Subcase 3.1: When n0mod3, apart from the monochromatic edges obtained as in Subcase 2.1 of Theorem 2.12, we obtain n3 additional monochromatic edges of the form vvi. Hence, the equitable defective number is bχek(Kn+1)+n+n3.

Subcase 3.2: When n1mod3, apart from the monochromatic edges obtained as in Subcase 2.2 of Theorem 2.12, we obtain n3 monochromatic edges of the form vvi. Further, there are two additional monochromatic edges of the form vivj, and hence, the equitable defective number is bχek(Kn+1)+n+n3+2.

Subcase 3.3: When n2mod3, along with the monochromatic edges obtained as in Subcase 2.3 of Theorem 2.12, we obtain n3 monochromatic edges of the form vvi and one monochromatic edge of the form vivj. Hence, the equitable defective number is bχek(Kn+1)+n+n3+2.

Case 4: When k4, follow the same coloring procedure as in Case-3 of Theorem 2.12 by considering the equitability condition, which is illustrated in Figure 12. We observe that the resulting monochromatic edges are only from the clique. Hence, the equitable defective number is bχek(Kn+1)◻

Figure 12 illustrates the ENP k-coloring of the total graph of gear graphs.

Figure 12 An ENP 4-coloring of total graph of gear graphs

3. Conclusion

In this paper, we explored the ENP k-coloring of the line, middle, and total graph of some graph classes and investigated the equitable defective number with respect to the ENP k-coloring. This study can be extended to different graph classes and many other derived graphs. Moreover, the central graph of all these graph classes can also be discussed. Further investigations can be done in powers of graphs and different graph products.

Acknowledgements

The authors would like to gratefully acknowledge the critical and constructive comments made by the reviewers which has elevated the standards of the paper significantly. They also acknowledge their co-researcher Ms. Phebe Sarah George for her inputs which refined the content of this paper.

Declarations

The authors declare no conflict of interest.

References:

  1. F. Harary. Graph theory, volume 2. Narosa Publ. House, New Delhi, 1996.
  2. S. Jose and S. Naduvath. On equitable near proper coloring of graphs. Communications in Combinatorics and Optimization, 9(1):131–143, 2024. https://doi.org/10.22049/cco.2022.27240.1218.
  3. S. Jose and S. Naduvath. On equitable near proper coloring of Mycielski graph of graphs. In Data Science and Security, pages 331–339. Springer, 2021. https://doi.org/10.1007/978-981-16-44863_37.
  4. S. Jose and S. Naduvath. On equitable near proper coloring of certain graph classes. AIP Conference Proceedings, 2516(1):210036, 2022. https://doi.org/10.1063/5.0108430.
  5. S. Jose and S. Naduvath. On equitable near proper coloring of derived graph classes. Carpathian Mathematical Publications, 14(2):529–542, 2022. https://doi.org/10.15330/cmp.14.2.529-542.
  6. K. Kaliraj and V. V. Joseph. On equitable coloring of helm graph and gear graph. International Journal of Mathematical Combinatorics, 4:32–38, 2010.
  7. K. Kaliraj, V. V. Joseph, and A. A. M. Moideen. On equitable coloring of sunlet graph families. Ars Combinatoria, 103:497–504, 2012.
  8. J. Kok and S. Naduvath. δ(k)-colouring of cycle related graphs. Advanced Studies in Contemporary Mathematics, 32(1):113–120, 2022. https://arxiv.org/abs/1807.01915v1.
  9. W. Meyer. Equitable coloring. The American Mathematical Monthly, 80(8):920–922, 1973.
  10. D. West. Introduction to graph theory, volume 2. Prentice Hall of India, New Delhi, 2001.