A proper coloring assigns distinct colors to the adjacent vertices of a graph. An equitable near proper coloring of a graph 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 for which is equitably colorable is known as the equitable
chromatic number denoted by .
An improper coloring or a defective coloring of
allows the adjacent vertices to
receive the same colors. The resulting monochromatic edges are also
called bad edges. A near proper coloring of 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 -coloring) of a graph is a defective coloring in which the
set of vertices of can be
partitioned into color classes
such that for any 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 -coloring of
is defined as equitable
defective number and is denoted by .
In an ENP coloring, the vertex set is partitioned into color classes by the integer
partitioning of , the order of the
graph such that where and
is the cardinality of the -th color class of . 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 are excluded from this discussion, as
coloring a graph with only one color makes all edges monochromatic.
Hence, we consider the cases when .
Throughout the discussion, be the
available colors, and are the corresponding color classes. In an ENP-coloring,
all possible values for where
are
considered. The function
represents the color assigned to the vertex . The monochromatic edges resulting
from an ENP -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
-coloring of line graph, middle
graph and total graph
Let be a graph with vertex set
and edge set . The line graph of , denoted by , is the graph whose vertex set is
the edge set of with two vertices
of that are adjacent whenever
the corresponding edges of are
adjacent.
The middle graph of ,
denoted by , is the graph whose
vertex set is , where
two vertices in are adjacent
if and only if they are either adjacent edges of or one is a vertex and the other is an
edge incident with it.
The total graph of ,
denoted by , has vertex set
, and the edges join
all elements of this vertex set that are adjacent or incident in .
This paper discusses the ENP -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 be the available colors and be the
corresponding color classes. In an ENP -coloring, we consider all possible
cases for where . The bad edges
resulting from an ENP -coloring
are represented by dotted lines.
2.1. ENP -coloring of path graph families
The line graph of a path graph of order is a path graph of order , and hence the equitable chromatic
number is . In an ENP -coloring, we consider only the graphs
with , 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 -coloring of the middle graph of a path
graph.
Theorem 2.1.
For a path where , .
Proof. Consider and . Then,
.
Thus, contains vertices, and observe that . In an ENP -coloring, only one case is to be considered.
It is possible to partition the vertex set into two subsets, and . Now,
assign the vertices in with the
color and with the color . Since forms a path of order , , as monochromatic edges are formed among
the vertices .
Another possible way of an ENP -coloring is defined as follows:
This coloring results in
monochromatic edges of the form or . It also yields in monochromatic edges, and thus .
Figure 1 depicts an ENP -coloring of the middle graph of
paths.
Figure 1 M with ENP 2-coloring
The total graph of a path contains vertices and . The succeeding theorem
addresses the ENP -coloring of the
total graph of paths when .
Theorem 2.2.
For a path where , .
Proof. Let ,
and in an ENP -coloring, the below
situations are investigated.
Case 1: When is even, we partition the vertex set
as follows:
and .
Case 2: When is odd, is partitioned as below:
and .
In both cases, it is evident that . Now, assigning the
vertices of with the color
and with the color , we observe that every edge is a monochromatic edge, and hence the equitable
defective number is .
Figure 2 depicts an ENP -coloring of the total graph of
paths.
Figure 2 . T with ENP 2-coloring
2.2. ENP -coloring of cycle graph families
The line graph of a cycle is
the cycle itself. Hence, the
equitable chromatic number is
when is even and when is odd. When and is odd, the equitable defective number
is .
The subsequent theorem examines the ENP -coloring of the middle graph of cycles
for .
Theorem 2.3.
For a cycle , .
Proof. Let and . Now, , and
note that , and
thus the ENP -coloring considers
only one case . In the first
possible ENP -coloring, assign all
of the vertices and with the colors and respectively, and it can be observed
that every edge between the vertices is a monochromatic edge, and thus the
equitable defective number is .
The second possible ENP -coloring may be performed as in Theorem
2.1, and this coloring also produces
monochromatic edges.
Additionally, there are
monochromatic edges of the form for even ;
however, for odd , there are monochromatic edges of the form and one monochromatic edge. Thus,
.
Figure 3 depicts an ENP -coloring of the middle graph of
cycles.
Figure 3 An ENP 2-coloring of middle graph of cycles
The following theorem describes the ENP -coloring of the total graph of a cycle.
Theorem 2.4.
For where ,
Proof. Note that when and otherwise. Hence, the following cases
need to be addressed here.
Case 1: Assume that and is even. We partition the vertex set so
that and .
Now, , and every edge, where , is a monochromatic edge.
Thus, the equitable defective number is .
Case 2: Assume that and is odd. Let us partition the vertex set
such that and . Here, and monochromatic edges are obtained
connecting and . Furthermore, another and monochromatic edges are
obtained. Thus, the equitable defective number, in this case, is (see Figure 4 for illustration).
Case 3: When and , assign the vertices with the three
available colors in a cyclic order by considering the equitability
condition. Here, the equitable defective number is .
Figure 4 depicts an ENP -coloring of the total graph of
cycles.
Figure 4 An ENP 2-coloring of total graph of cycles
2.3. ENP -coloring of sunlet graph families
A sunlet graph denoted by is obtained by attaching pendant edges to a cycle . ENP -coloring of sunlet graphs is discussed
in [4]. In a sunlet
graph, the vertices corresponding to are termed as rim vertices.
The following theorem investigates the ENP -coloring of the line graph of a sunlet
graph.
Theorem 2.5.
The equitable defective number of , where , is .
Proof. Consider ,
where induces a cycle of order
, and are the vertices that are adjacent
with both and . The equitable coloring of contains colors (see [7]), and thus, in an ENP -coloring, only one case as is considered. Let and be the two available colors, and the
following cases need to be considered.
Case 1: Let be even. Then, the vertices can be properly colored with the two available
colors. When the remaining vertices are assigned the same colors
equitably, monochromatic edges
are obtained between and .
Case 2: Let be odd and follow the same coloring
procedure as in Case 1. That is, assign with the color , with the color , and so on. Since is odd, both and receive the same color, and thus
there is a monochromatic
edge on the rim. Now, the vertex adjacent to both and receives an alternate color from the
color assigned to both of them. Further, the remaining vertices can be
assigned in an equitable manner. Thus, monochromatic edges are obtained
between the vertices and , and the equitable defective number
is .
Combining the above two cases, .
An ENP -coloring of the line
graph of sunlet graphs is illustrated in Figure 5.
Figure 5 An ENP 2-coloring of sunlet graphs
An ENP -coloring of the middle
graph of a sunlet graph for distinct values of is discussed in the next theorem.
Theorem 2.6.
For a sunlet graph
, where ,
Proof. Consider . Here, the vertices forms an inner – cycle termed as the rim vertices of
, and each ; is connected to the corresponding ; forms an outer –
cycle. Again, are the pendant vertices
connected to the corresponding . Recall that (see [7]), and in an ENP -coloring, two cases are to be
considered as and .
Case 1: Assume and we partition the vertex set as
follows.
and . Assign the vertices in with the color and with the color . Now, , and monochromatic edges generated among the
vertices . Additionally, the
vertices and have monochromatic edges connecting them,
where . Thus, the
equitable defective number is .
Case 2: Let . Among the vertices of , vertices are on the rim. Assign all
the rim vertices with the three available colors, say , , and , in a cyclic order, and consider the
following three subcases.
Subcase 2.1: When , , and assign the
rim vertices with the three colors in a cyclic order such that each
color repeats exactly
times without creating any monochromatic edges. Now, assign the vertices
with the same color
received by the vertices , and
monochromatic edges are obtained
in between the vertices and
. Further, the vertices can be equitably assigned these
three colors without creating monochromatic edges. Thus, there are monochromatic edges.
Subcase 2.2: When , , follow the
same coloring procedure for the rim vertices and where creates a monochromatic edge. Since , to attain the
equitability, color can be
assigned to . The remaining
; () can receive the same
color received by to obtain
monochromatic edges of the form
(). Further, each ; () can be received any of the three colors
equitably with the condition that and the corresponding receive different colors leading
to the equitable defective number as .
Subcase 2.3: When , , and the rim
vertices follow the same coloring pattern as in the previous subcases
leads to a monochromatic
edge. Further, the remaining vertices and can receive any of the three
colors by considering the equitability condition, creates monochromatic edges as in Subcase
2.2. Hence, the equitable defective number in this case is .
Thus, combining the above three subcases, .
An ENP -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 -coloring of the total graph of sunlet
graphs for different parities of
and for .
Theorem 2.7.
For where ,
Proof. Consider the vertex sets and the adjacencies as in
Theorem 2.6. Observe that (see [7]); thus, in an ENP -coloring, the following cases need to
be considered.
Case 1: When , repeat the same coloring procedure
as in Case-1 of Theorem 2.6, and we obtain the equitable
defective number as .
Case 2: When , 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 , monochromatic edges are obtained of the
form as in Theorem 2.6.
Subcase 2.2: When , two
monochromatic edges are obtained, one among the vertices and one among the vertices . Apart from that, the vertices and have
monochromatic edges connecting them. Thus, the equitable defective
number is . (See Figure for reference.)
Subcase 2.3: When , we get the same
monochromatic edges as in
Subcase 2.2 and an additional monochromatic edge . Thus, the equitable defective
number is . (refer to Figure 7 for
illustration.)
An ENP -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 -coloring of star graph families
The line graph of a star graph is a complete graph of order
. The ENP -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 , the equitable defective
number is given by where and is the number of color classes with
maximum cardinality.
The following theorem describes the ENP -coloring of the middle graph of star
graphs.
Theorem 2.9.
For ,
Proof. Consider and .
Consider as the
corresponding vertex set of . These edges form a clique of
order in , and hence as the vertices
induce a
complete graph of order . Thus,
in an ENP -coloring, and the following cases
need to be considered.
Case 1: When and , assign the
available colors, say alternately to the
vertices . Now, color the
vertices so that each and the
corresponding receive different
colors in an equitable manner. Also, assign the vertex with any available colors such that
receives the least used color
assigned to the vertices .
Since,
induces a clique of order , the
equitable defective number in this case is .
Case 2: When , assign the vertices using the colors, and the corresponding vertices
can be assigned using the same
colors such that both and the
corresponding receive different
colors, and as a result of this assignment no monochromatic edges
obtained. Further, assign the vertex with any available colors; only one
monochromatic edge is
obtained, and thus the equitable defective number is .
Figure 8 depicts an ENP -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 and for various values of .
Theorem 2.10.
For the total graph
of a star graph where ,
Proof. Consider the vertices as in Theorem 2.9. Note that as induces a clique
of order . The vertices induce a clique of
order , and let be the vertices that
are adjacent to ,
respectively. In , the
vertex is adjacent to all the
vertices and (). The ENP -coloring of complete graphs is
discussed in Theorem 2.8. Hence, the following cases
need to be addressed here.
Case 1: When , assign the two available colors, say
and , for every alternate vertex of the
complete graph. Further, if (or ), then assign (or ). Now, or , and based on this assignment, the
following observations are to be noted.
When is even, monochromatic edges of the
form and monochromatic edges of the
form are obtained. When is odd, we get monochromatic
edges of the form and monochromatic
edges of the form .
Consequently, in both cases, the equitable defective number is .
Case 2: When and , we can assign all the vertices with the available colors in an equitable manner
as follows. When the vertex set is partitioned into color classes, each color class
consists of either vertices or
vertices. If the vertex is placed
in the color class with minimum cardinality , we obtain
monochromatic edges. Hence, together with the monochromatic edges from
, the equitable defective number
is .
Case 3: When , we can properly color the complete graph of order with the available colors, and the vertices
can also be
properly colored with these
colors. Further, assign the vertex with any of the available colors, from which we obtain
two monochromatic edges.
Figure 9 depicts the ENP -coloring of the total graph of star
graphs.
Figure 9 An ENP 3-coloring of total graph of star graphs
2.5. ENP -coloring of gear graph families
A gear graph,
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 -coloring of the line graph of a gear
graph for different parities of .
Theorem 2.11.
For ,
Proof. Let
and
such that , , and . Consequently,
.
Since form a clique of order in , . Subsequently, in an
ENP -coloring, consider and address the
following cases.
Case 1: Assume and assign the vertices with the two available colors, say
and 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
with the same available
colors in a cyclic order satisfying the equitability condition, and we
obtain monochromatic edges in
between the vertices and . Thus, gives the equitable
defective number in this case.
Case 2: When , assign the vertices with the available colors, monochromatic edges are
obtained. By the definition of , each is adjacent to two distinct vertices
, which forms a that can be colored properly using
the three available colors such that each vertex of receives different color. This
assignment of colors does not create any additional monochromatic edges;
therefore, the equitable defective number is .
An ENP -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 and
distinct values of , the theorem
below discusses the ENP -coloring
of the middle graph of gear graphs.
Theorem 2.12.
For ,
Proof. Consider .
Let such that , and . Consequently, . It is evident that the edges , along with the vertex form a clique of order , and thus (see [6]). In an ENP -coloring, consider and address the following
cases.
Case 1: Let
and consider the subcases as given below.
Subcase 1.1: When is even, partition the vertex set into
two subsets as follows.
Let .
.
Now, . Hence, the central vertex can be placed into any one of the color
classes, resulting in . Further, assign the vertices in the set with the color and with the color . As a result of this assignment of
colors, we obtain monochromatic
edges of the form and . Also, the vertices and have monochromatic edges connecting them,
of the form , where and there is a monochromatic edge . Further, monochromatic edges are obtained in
between the vertices of the
form , where . Furthermore, together with the monochromatic
edges from the complete graph that is investigated in Theorem 2.8, the equitable defective number
is .
Subcase 1.2: When is odd, let us partition the vertex set
as follows.
Let .
.
Assign the vertices in with
the color and with the color . Now, and the
vertices and have monochromatic edges connecting them,
of the form , where . Moreover, the vertices and have monochromatic edges connecting them of
the form and . Furthermore, a
monochromatic edge and
monochromatic edges among the
vertices of the form are generated, where . Now, along with the monochromatic edges
obtained in the ENP -coloring of
complete graphs, the equitable defective number is .
Case 2: When , the following subcases are to be
addressed.
Subcase 2.1: Let . Assign the vertices on the outer rim ( and ) using the three available colors in a cyclic order.
Further, color the inner rim vertices () in the same cyclic order using the three colors such
that both and receive the same color. Then, assign
with any one of the three colors.
It can be observed that along with the monochromatic edges obtained from
the complete graph, the vertices and generate monochromatic edges of the form and . Thus, the
equitable defective number is (see Figure 11 for illustration).
Subcase 2.2: Let . Repeat the same coloring procedure as
in Subcase 2.1 for the outer rim vertices and where , except for one vertex. Since , the
additional vertex on the outer rim can be assigned the color . Further, the inner rim vertices can
also be assigned as in Subcase 2.1, and since , the additional
vertex on the inner rim can be received the color . Further, the vertex can receive the color 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 .
Subcase 2.3: Let . 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 and 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 and respectively. Finally, the vertex
can receive the color to maintain the equitability
constraint. In comparison with Subcase 2.1, we get an additional
monochromatic edge of the form . Therefore, the equitable
defective number is (see Figure 11).
Case 3: When , the vertices , and can be assigned properly using the available colors. Now the vertex 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
Figure 11 represents the ENP
-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 -coloring of the total graph of gear
graphs for different parities of
and various values of .
Theorem 2.13.
For the total graph of a gear graph ,
Proof. Note that and (see [6]). The following observations
are made when the same coloring procedure is followed, as in Theorem 2.12.
Case 1: When and is even, apart from the monochromatic
edges obtained as in Subcase-1.1 of Theorem 2.12, monochromatic edges are obtained of
the form , where along with a monochromatic edge . Further, there are monochromatic edges
connecting and . Thus, the equitable defective number
is .
Case 2: When and is odd, along with the monochromatic
edges obtained as in Subcase-1.2 of Theorem 2.12, we may
obtain monochromatic edges of the
form , where and another monochromatic edge also obtained. Further, there
are
monochromatic edges connecting the vertices and . Hence, the equitable defective number
is .
Case 3: When , we have the below observations.
Subcase 3.1: When , apart from the monochromatic edges
obtained as in Subcase 2.1 of Theorem 2.12, we
obtain additional
monochromatic edges of the form . Hence, the equitable defective
number is .
Subcase 3.2: When , apart from the monochromatic edges
obtained as in Subcase 2.2 of Theorem 2.12, we
obtain
monochromatic edges of the form . Further, there are two additional
monochromatic edges of the form , and hence, the equitable
defective number is .
Subcase 3.3: When , along with the monochromatic edges
obtained as in Subcase 2.3 of Theorem 2.12, we
obtain
monochromatic edges of the form and one monochromatic edge of the
form . Hence, the equitable
defective number is .
Case 4: When , 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 .
Figure 12 illustrates the ENP
-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 -coloring of the line, middle, and total
graph of some graph classes and investigated the equitable defective
number with respect to the ENP -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:
F. Harary. Graph theory, volume 2. Narosa Publ. House, New Delhi, 1996.
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.
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.
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.
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.
K. Kaliraj and V. V. Joseph. On equitable coloring of helm graph and gear graph.
International Journal of Mathematical Combinatorics, 4:32–38, 2010.
K. Kaliraj, V. V. Joseph, and A. A. M. Moideen. On equitable coloring of sunlet graph families.
Ars Combinatoria, 103:497–504, 2012.
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.
W. Meyer. Equitable coloring.
The American Mathematical Monthly, 80(8):920–922, 1973.
D. West. Introduction to graph theory, volume 2. Prentice Hall of India, New Delhi, 2001.