International Journal of Analysis and Applications Volume 18, Number 6 (2020), 1108-1122 URL: https://doi.org/10.28924/2291-8639 DOI: 10.28924/2291-8639-18-2020-1108 MONOTONE CHROMATIC NUMBER OF GRAPHS ANWAR SALEH1,∗, NAJAT MUTHANA1, WAFA AL-SHAMMAKH1, HANAA ALASHWALI2 1Department of Mathematics, Faculty of Science, University of Jeddah, Jeddah, Saudi Arabia 2Department of Mathematics, King Abdulaziz University, Jeddah, Saudi Arabia ∗Corresponding author: asaleh1@uj.edu.sa Abstract. For a graph G = (V, E), a vertex coloring (or, simply, a coloring) of G is a function C : V (G) → {1, 2, ..., k} (using the non-negative integers {1, 2, ..., k} as colors). In this research work, we introduce a new type of graph coloring called monotone coloring, along with this new coloring, we define the monotone chromatic number of a graph and establish some related new graphs. Basic properties and exact values of the monotone chromatic number of some graph families, like standard graphs, Kragujevac trees and firefly graph are obtained. Also, we get a characterization for bipartite graphs by defining the monotone bipartite graph. Exact values of the monotone chromatic number for some special case of Cartesian product of graphs are found. Finally, upper and lower bounds for monotone chromatic number of the Cartesian product for non trivial connected graphs are presented. 1. Introduction Throughout this research work, by graph we mean finite graph without loops and parallel edges. Any notations or terminology not specifically defined here, we refer the book [6]. More details about coloring in graph and its related are reported in ( [3, 8]). Two interesting types of coloring are introduced and studied in ( [1, 2, 5]). As usual, Pn,Cn,Kn and Wn are the n−vertex path, cycle, complete, and wheel graph, respectively, Kr,s is the complete bipartite graph on r+s vertices and Sr is the star graph with r+ 1 vertices. Received September 21st, 2020; accepted October 19th, 2020; published November 17th, 2020. 2010 Mathematics Subject Classification. 05C76, 05C22, 05C15. Key words and phrases. monotone coloring; monotone chromatic number; monotone clique set; montone bipartite graph; complete monotone graph. ©2020 Authors retain the copyrights of their papers, and all open access articles are distributed under the terms of the Creative Commons Attribution License. 1108 https://doi.org/10.28924/2291-8639 https://doi.org/10.28924/2291-8639-18-2020-1108 Int. J. Anal. Appl. 18 (6) (2020) 1109 Graph coloring is one of essential concepts in the theory of graphs. It has preoccupied a large number of people as a distraction puzzle during the 19th century and later in the framework of scientific research, since this conception exhibits a significant interest from a theoretical and practical point of view. Many applications are modeled and investigated with the use of graph coloring. For a graph G = (V, E), a vertex coloring (or, simply, a coloring) of G is a function C : V (G) →{1, 2, ...,k} (using the non-negative integers {1, 2, ...,k} as colors). The huge applications of coloring motivated us to introduce a new type of graph coloring called monotone coloring of the graph, we define the monotone chromatic number of a graph, complete monotone graph and monotone clique set of a graph. Some basic properties and relations with the other graph parameters and exact values of the monotone chromatic number of some graph families, like standard graphs, firefly graph and Kragujevac trees obtained. Also, we get a characterization for bipartite graphs by defining the monotone bipartite graph. Exact values of the monotone chromatic number for some special case of Cartesian product of graphs are found. Lastly upper and lower bounds for monotone chromatic number of the Cartesian product for non trivial connected graphs are presented. 2. Monotone Chromatic Number of Graphs In this section, we define the monotone chromatic coloring and monotone chromatic number of a graph and give several preliminary results and straightforward facts regarding the monotone coloring of graphs. Also we found the monotone chromatic number for some families of graphs. Definition 2.1. Let G = (V,E) be a graph. A path P = [v1,v2, ...,vk+1] in G is a monotone path if either deg(vi) ≤ deg(vi+1) or deg(vi) ≥ deg(vi+1) for all i = 1, 2, ...,k. Any two vertices u and v in G are called monotone adjacent if there exists a monotone path connected them. Definition 2.2. A monotone k− coloring of the graph G is coloring the vertices of G with k colors such that no two monotone adjacent vertices share the same color. The smallest integer k such that G has a monotone k− kcoloring is called the monotone chromatic number of G and denoted by χmo(G). A graph G is said to be monotone k− colorable if it has monotone k− coloring. Monotone coloring as function we can define as: Definition 2.3. The monotone coloring function is a function f : V (G) → 1, 2, 3, ...,k ⊆ N which satisfy that for any two monotone adjacent vertices v and u, f(v) 6= f(u). Proposition 2.1. Int. J. Anal. Appl. 18 (6) (2020) 1110 (1) For any path Pn with n ≥ 2 vertices, χmo(G) =   2, if n = 2;n− 1, if n ≥ 3. (2) For any connected regular graph G with n ≥ 3 vertices, χmo(G) = n. (3) For any complete bipartite graph Kr,s, where 1 < r ≤ s, we have χmoKr,s = 2. (4) For any wheel graph G ∼= Wr with r + 1 vertices, χmo(G) = r + 1. (5) For any book graph G ∼= Bm, we have χmo(G) = 4. (6) For any helm graph G ∼= Hn with 2n + 1 vertices, χmo(G) = n + 2. (7) For any gear graph G with 2n + 1 vertices, we have χmo(G) =   4, if n = 3;3, if n ≥ 4. From the definition of the proper coloring and monotone coloring, it is obviously, that any monotone coloring is proper coloring but the converse is not true. As any two adjacent vertices in any graph are also monotone adjacent, then we have the following result. Proposition 2.2. For any graph G, χ(G) ≤ χmo(G). The equality hold if and only if any two monotone adjacent vertices are adjacent. Proposition 2.3. (1) For any monotone χmo(G)− coloring of any graph G, all the very weak vertices has the same color. (2) For any nontrivial connected graph G with n vertices, 2 ≤ χmo(G) ≤ n. (3) For any graph G ∼= ∪ri=1Gi, we have, χmo(G) = max{χmo(Gi) : i = 1, 2, ...r}. Remark 2.1. Let G and H be any two graphs such that H is subgraph of G. Then the monotone chromatic number of G and H are not comparable. That means all the possibilities allowed. According to the monotone adjacency between vertices, we define the monotone bipartite graph, and complete monotone graph. Definition 2.4. A bipartite graph G is called monotone bipartite graph if and only if any monotone path in G is of length at most one. The definition of monotone bipartite graph characterize the trees into two families monotone trees and non-monotone trees The double star graph denoted by B(r,s) with r+s+ 2 vertices, is a tree that containing exactly two non-pendent vertices. Int. J. Anal. Appl. 18 (6) (2020) 1111 Proposition 2.4. For any double star graph G ∼== B(r,s) with r + s + 2 vertices, such that r < s, χmo(G) = 3. Theorem 2.1. Let G be any graph. Then G is monotone bipartite graph if and only if χmo(G) = 2. Proof. Let G be a graph such that χmo(G) = 2 and suppose contrary that there is monotone path uvw of length 2, we need at least three colors for monotone coloring of G that means χmo(G) ≥ 3 which is a contradiction. Therefore any monotone is of length at most one. Hence G is monotone bipartite graph. To prove the other direction, suppose, that G is monotone bipartite graph. Then the result coming from the Proposition 2.2. � Corollary 2.1. For any monotone tree Tn with n vertices, χmo(G) = 2. Proposition 2.5. For any connected graph G with n ≥ 3 vertices , χmo(G) = 2 If and only if for any vertex v ∈ V (G), either v is very strong or very weak. Proof. Suppose that χmo(G) = 2, and assume in contrary that, there is a vertex v ∈ V (G) which is neither very strong nor very weak. Then we have two cases: Case 1 : if deg(v) = 1, then v is very weak which contradict our assumption. Case 2: if deg(v) 6= 1, then v must belongs to some path say uvw such that deg(u) < deg(v) < deg(w) or deg(u) = deg(v) = deg(w) or one of the vertices u, or w has the same degree as v. For all of these cases, it needs at least 3 colors to monotone coloring which contradicts that χmo(G) = 2. Now, suppose that for any vertex v ∈ V (G), either v is very strong and one very weak. So, any monotone path will contains only two vertices; one of them is very weak and the other is very strong. Hence χmo(G) = 2. � Corollary 2.2. A connected graph G = (V ; E) is monotone bipartite graph if and only if any vertex v ∈ V (G) is either very strong or very weak. Proposition 2.6. For any connected graph G with n ≥ 2 vertices , χmo(G) = n If and only G is complete monotone graph. Proof. let G be a monotone complete graph with n vertices and suppose that G in contrary not satisfy the condition G contains at most either one very weak or one very weak vertex. Suppose the vertex set V (G) = {v1,v2, ...,vn}, such that v1 is very weak vertex, then if there is another very weak vertex say vi, then there is no monotone vertex between v1 and vi which is a contradiction with the definition of the monotone complete graph, similarly if there is very strong vertex say vj ,then there is no monotone path Int. J. Anal. Appl. 18 (6) (2020) 1112 between v1 and at least one of the neighborhood of the vertex vj . The proof in the same way if we suppose v1 is very strong. Hence G contains at most either one very weak or one very weak vertex. To prove the other direction. Suppose G contains at most either one very weak or one very strong vertex. then clearly there exist a monotone path containing all the vertices that means between any two vertices there is a monotone. Hence G is monotone complete graph. � Definition 2.5. A subset X ⊆ V (G) of size k is called a monotone k− clique of G if between any two vertices u and v in the set X there is a monotone path. The monotone clique number of G denote by ωmo(G) is the largest positive integer k such that G contains a monotone k− clique. The monotone clique set with size ωmo(G) is called maximum monotone clique. Definition 2.6. ( [4]) Let P3 be the 3− vertex tree, rooted at one of its terminal vertices. For k = 2, 3, ·,k; construct the rooted tree Bk by identifying the roots of k copies of P3 . The vertex obtained by identifying the roots of P3−trees is the root of Bk. Definition 2.7. ( [4]) Let d ≥ 2 be an integer.Let β1,β21, · · · ,βd, be rooted trees,specified in Definition 2.6, i.e., β1,β2, · · · ,βd ∈ {B2.B3, ...}. A Kragujevac tree T is a tree possessing a vertex of degree d, adjacent to the roots of β1,β1, · · · ,βd. This vertex is said to be the central vertex of T , whereas d is the degree of T. Theorem 2.2. Let G ∼= Kgd,k, where Kgd,k is the Kragujevac tree of degree d ≥ 2 and with branches BKi ,i = 1, 2, ..., where every branch BKi contains ki pendant vertices and if t is the number of branches BKi where d = ki . Then χmo(G) =   3, if the central vertex is very weak vertex; 4, if the central vertex is very strong vertex; 5, if the central vertex is very typical vertex; d + 3, if the central vertex is regular vertex; t + 4, if the central vertex is weak or strong vertex; t + 5, if the central vertex is typical vertex. Proof. Let G be the Kragujevac tree Kgd,k of degree d ≥ 2 with enteral vertex v and with branches BKi ,i = 1, 2, · · · , where every branch BKi contains ki pendant vertices and if t is the number of branches BKj where d = kj . we have 7 possibilities for the type of the central vertex v of the Kragujevac tree: Case 1. The central vertex v is very strong, in this case, we can define monotone coloring function by partition the vertex set of the tree into 4 classes, first class, the pendant vertices, second class the support vertices and third class the roots vertices of the branches and fourth class the central vertex and give color for each class, that means χmo(G) ≤ 4 and it is not difficult to see that, any set contains the the pendent Int. J. Anal. Appl. 18 (6) (2020) 1113 vertex with its support vertex and the root vertex in any branch along with the central vertex v is clique set with 4 vertices. That means in this case χmo(G) = 4. Case 2. The central vertex v is very weak, then we can define monotone coloring function Cmo by partition the vertex set into 4 subsets, S1 is the pendant vertices, S2 the support vertices and S3 be the roots vertices of the branches and S4 be the central vertex v and giving color for each subset as following: Cmo(x) =   i, if x ∈ Si and x not the central vertex;1 or 2, if x is the central vertex. Therefore, χmo(G) ≤ 3 and since the set of vertices in any path between the pendant vertex of any branch and its root vertex is monotone clique set. Hence in this case χmo(G) = 3. Case 3. The central vertex v is regular vertex, then in this case, let us partition the vertex set into three subsets; the set of pendant vertices S1, the support vertices S2 and the set of roots vertices with the central vertex S4, we define a monotone coloring function which assign d + 1 different colors to the vertices of S3 and one color to all the vertices of S2 and another different color to the vertices of S1, so, we need to d + 3 colors to this monotone coloring function, therefore χmo(G) ≤ d + 3. Obviously, if we take any pendant vertex along with its support vertex in any branches along with the set S3 will make monotone clique set of G of size d + 3. Hence χmo(G) = d + 3. Case 4. The central vertex v is weak vertex, in this case, let us partition the vertex set into the following subsets of vertices, S1, the set of pendant vertices, S2 the set of support vertices, S3 the central vertex and the set of root vertices of degree equal to d and S4 the set of root vertices with degree greater than d. Now, |S3| = t + 1, we define monotone coloring function by assigning one color say 1 to the vertices of S1 and another color say 2 to the vertices of S2 and assign t + 1 different colors to the t + 1 vertices in S3 and assign one other color to the vertices in S4. So we need to t + 4 colors in this monotone coloring function and therefore, χmo(G) ≤ t + 4. Also, it is obviously to see that the vertices of S3 with one pendent vertex with its support vertex and one root vertex from S4 will make clique set in G. Hence χmo(G) = t + 4. Case 5. The central vertex v is strong vertex, in this case let us partition the vertex set into the following subsets of vertices; S1 the set of pendant vertices, S2 the set of support vertices S3 the central vertex with the set of root vertices of degree equal to d and S4 the set of root vertices with degree less than d. Now, if the number of root vertices with degree d is t, we define monotone coloring function by assigning one color say 1 to the vertices of S1 and another color say 2 to the vertices of S2 and assign t + 1 different colors to the t + 1 vertices in S3 and assign one other color to the vertices in S4. So we need to t + 4 colors in this monotone coloring function and therefore, χmo(G) ≤ t + 4. Also, obviously the set of vertices in S3 with the pendant vertex and its support vertex from any branch Bki with ki = d and the root vertex of any other branch Bki with ki ≤ d make a clique set in G with size t + 4. Hence χmo(G) = t + 4. Int. J. Anal. Appl. 18 (6) (2020) 1114 Case 6. The central vertex v is very typical vertex. Suppose there are s root vertex with degree less than d. Let S1 be the set of pendant vertices, S2 the set of support vertices S3 the set of roots vertices with degree less than d and let S4 be the root vertices of degree greater than d and S5 contains the central vertex. We can define monotone coloring function by assigning for any vertex x ∈ Si the color i; Cmo(x) = i. That means χmo(G) ≤ 5. Also the set which contains one vertex along with its support vertex and the root vertex in the same branch Bki where ki ≤ d and the central vertex and one root vertex from any branch Bki where ki ≥ d is clique set of size 5. Hence in this case χmo(G) = 5. Case 7. The central vertex v is typical vertex. Suppose there are t root vertex with degree equal to d. Let S1 be the set of pendant vertices, S2 the set of support vertices S3 the set of roots vertices with degree equal to d and let S4 be the root vertices of degree greater than d and S5 be the roots vertices of degree less than d, S6 contains the central vertex. We construct monotone coloring function by assigning one color to the vertices in S1 and another different color to the vertices in S2 and t + 1 different colors for the vertices in S3 and S6 also one other different color to the vertices in S4 and one different color to the vertices in S5. Therefore χmo(G) ≤ t + 5. Now, we have clique set of size t+ 5 which contains one pendant vertex, support vertex and root vertex from any of the branch Bki , where ki < d and the t vertices of S3 along with the central vertex, one root vertex from any branch Bki , where ki > d. Hence χmo(G) = t + 5. � Theorem 2.3. For any nontrivial connected graph G, with monotone chromatic number χmo(G), there exist at least one maximum monotone clique set with size ωmo(G) = χmo(G). Proof. Let G be any nontrivial connected graph with monotone chromatic number χmo(G) = s. Suppose to the contrary, that we have maximum clique set A with size |A| = ωmo(G) = t, where either t < s or t > s. Case 1. If t < s. Then there exists at least one coloring class say B and at least one monotone path between every two elements one from A and one from B which is contradict that A is the monotone clique with maximum size. Case 2. If t > s, then at least we need to t + 1 colors for monotone coloring which is contradict that χmo(G) = s. Hence, ωmo(G) = χmo(G). � Theorem 2.4. Let G ∼= Km1,m2···mk , where m1 ≤ m2 ≤ ··· ≤ mk be any complete k− partite graph and there are ti partite sets of the same number of vertices λi, where i = 1, 2, · · · ,s for some positive integer i. Then χmo(G) = k + s∑ i=1 ti(λi − 1). Proof. Let G ∼= Km1,m2···mk , where m1 ≤ m2 ≤ ···≤ mk be any complete k− partite graph and there are ti partite sets of the same number of vertices λi, where i = 1, 2, · · · ,s for some positive integer i ,by reordering Int. J. Anal. Appl. 18 (6) (2020) 1115 the partite sets which they have different number of elements as V1,V2, · · ·Vk−∑s i=1 ti, we can define a monotone coloring function as the following. f : V (G) → [k + s∑ i=1 ti(λi − 1)], by assigning the color i for each vertex in Vi and assigning for each vertex in the equal parite sets to different colors that means assign ∑s i=1 tiλi different colors to the vertices in V − ∑s i=1 ti⋃ i=1 Vi. Clearly, the function f which defined above is monotone coloring function on G. Therefore, χmo(G) ≤ k + s∑ i=1 ti(λi − 1). (2.1) It is not difficult to check that the set which contains the vertices in∑s i=1 ti⋃ i=1 Vi, and only one vertex from each Vi will make clique set with k + ∑s i=1 ti(λi − 1). Thus, χmo(G) ≥ k + s∑ i=1 ti(λi − 1). (2.2) Hence by inequalities 2.1 and 2.2, we get, χmo(G) = k + s∑ i=1 ti(λi − 1). � Theorem 2.5. Let G be any connected graph with n ≥ 3 vertices and D is the set of distinct degrees of the vertices. Then G is monotone complete graph if and only if for any set of vertices with the same degree in G is clique set in G. Proof. Let G be monotone complete graph with n ≥ 3 vertices, since G is monotone complete, then ωmo(G) = n. Therefore V (G) is a monotone clique set contains all the vertices of G. If G is regular, then there is only one clique set containing all the vertices. Suppose the graph is not regular that means the set D is of size greater than or equal to 2. Let D = {k1,k2, . . . ,kt} for some integer t ≥ 2, also let C1,C2, . . . ,Ct be the sets of vertices of degrees k1,k2, . . . ,kt respectively. Suppose in contrary, that there exists one set Cj, 1 ≤ j ≤ t such that Cj not a monotone clique set, then there exist at least two vertices u and v which they are not monotone adjacent in G which is a contradict that V (G) is clique set. Similarly, let C1,C2, . . . ,Ct are monotone clique sets in G. suppose G is not monotone complete, then there Int. J. Anal. Appl. 18 (6) (2020) 1116 exist at least two vertices u and v not monotone adjacent if they are with the same degree, then they will belong to same set Cj, 1 ≤ j ≤ t which is a contradiction, similarly we will get a contradiction even if they have different degrees. � We recall, that in [7], a firefly graph Fs,t,l where s ≥ 0, t ≥ 0, n− 2s− 2t− 1 ≥ 0 is a graph of order n that consists of s triangles, t pendent paths of length 2 and l pendant edges sharing a common vertex (see Figure 1). Proposition 2.7. For any firefly graph G ∼= Fs,t,l, χmo(G) = 3. Figure 1. Firefly graph Proof. Let G ∼= Fs,t,l where s ≥ 0, t ≥ 0, n− 2s− 2t− 1 ≥ 0 be a firefly graph and by labeling the vertices as in Figure 1. By partition the vertex set into the following sun- sets of vertices, S1 = {w1,w2, . . . ,ws}, S2 = {w′1,w′2, . . . ,w′s}, S3 = {v1,v2, . . . ,vl}, S4 = {u1,u2, . . . ,ut}, S5 = {u′1,u′2, . . . ,u′t} and S6 is the central vertex. By defining the monotone coloring function f : V (G) −→{1, 2, 3} as following, f(x) =   1, if x ∈ S1 ∪S3 ∪S4; 2, if x ∈ S2 ∪S5; 3, x is the central vertex. Therefore, χmo(G) ≤ 3. The set of vertices in any triangle in the firefly graph generate a monotone clique set, that means χmo(G) ≥ 3. Hence, χmo(G) = 3. � Int. J. Anal. Appl. 18 (6) (2020) 1117 The corona product G1 ◦ G2 of two graphs G1 and G2, where V (G1),V (G2) are the set of vertices of G1,G2 respectively, is the graph obtained by taking |V (G1)| copies of G2 and joining each vertex of the i-th copy with the corresponding vertex u ∈ V (G1) [6]. Proposition 2.8. For any positive integer a ≥ 3, there exists a graph G such that χ(G) = a and χmo(G) = a + 1. Proof. Let G be a graph which construct by the corona product between the complete graphs Ka and K1. That means G ∼= Ka◦K1 where a ≥ 3. Then it is not difficult to see that χ(G) = a and χmo(G) = a+ 1. � Definition 2.8. A subset S ⊆ V is called monotone independent set, if the set S does not contains any monotone adjacent vertices. The maximum cardinality of the monotone independent set is called monotone independence number of the graph and denoted by βmo(G). For example; for any path Pn with n ≥ 3 vertices, βmo(Pn) = 2. The monotone independence number of any complete monotone graph is one. Theorem 2.6. Let G be a graph with n vertices and with monotone independence number βmo(G). Then χmo(G) ≥ n βmo(G) . Further, the equality holds if G is complete monotone graph. Proof. Let χmo(G) = k and let Cmo : V (G) −→ 1, 2, . . . ,k be monotone k-coloring function. Let βmo(G) be the monotone independence number of G. We define Vj = {v | Cmo(v) = j} for j = 1, 2, . . . ,k. Obviously, Vj is monotone independent set and clearly |Vj| ≤ βmo(G) and k∑ j=1 |Vj| ≤ kβmo(G) = χmo(G)βmo(G). (2.3) Also since k∑ j=1 |Vj| = n. (2.4) Thus, from inequalities 2.3 and 3.1 n ≤ χmo(G)βmo(G) ⇒ χmo(G) ≥ n βmo(G) . Also, if G is complete monotone graph, then βmo(G) = 1. Therefore, χmo(G) = n βmo(G) = n. � Int. J. Anal. Appl. 18 (6) (2020) 1118 3. Monotone Chromatic number for Some Cartesian Product of Graphs The Cartesian product G1�G2 of two graphs G1 and G2, where V (G1),E(G1) and V (G2),E(G2) are the sets of vertices and edges of G1 and G2, respectively, has the vertex set V (G1) × V (G2) and two vertices (u,u′) and (v,v′) are connected by an edge if and only if either (u = v and u′v′ ∈ E(G2)) or (u′ = v′ and uv ∈ E(G1)) [6]. Theorem 3.1. Let G ∼= Pr�Ps where r,s ≥ 3. Then χmo(G) = (r − 2)(s− 1) + 1. Proof. Let G ∼= Pr�Ps where r,s ≥ 3. By labeling the vertices of the graph G from the left to the right the first line L1 of the vertices by v1,1,v1,2, . . . ,v1,s−1,v1,s, the second line of the vertices v2,1,v2,2, . . . ,v2,s−1,v2,s and so on till line Lr−1 by vr−1,1,vr−1,2, . . . ,vr−1,s−1,vr−1,s and finally, the vertices of the line Lr by vr,1,vr,2, . . . ,vr,s−1,vr,s. let us make partition for the vertex set to the following subsets S1 = {v1,1,v1,s,vr,1,vr,s}. S2 = {vi,j : 1 < i < r, 1 ≤ j < s}. S3 = {v1,j,vr,j : 1 < j < s}. S4 = {vi,s : 1 < i < r}. We can define a monotone coloring function as following f(vi,j) =   1, if vi,j ∈ S1 ; (i− 2)s + j + 1, if vi,j ∈ S2; f(vj, 1), if vi,j ∈ S3 ; f(vj, 1), if vi,j ∈ S4. Clearly f is a monotone-k-coloring function, where k = (r − 2)(s− 1) + 1. So χmo(G) ≤ (r − 2)(s− 1) + 1. (3.1) The set S2 ∪{v1,1} is monotone clique set with (r − 2)(s− 1) + 1 vertices. Therefore, χmo(G) ≥ (r − 2)(s− 1) + 1. (3.2) Hence by inequalities 3.1 and 3.2, we get, χmo(G) = (r − 2)(s− 1) + 1. � Int. J. Anal. Appl. 18 (6) (2020) 1119 Theorem 3.2. Let G ∼= Cr�Ps, where r,s ≥ 3. Then χmo(G) = r(s− 1). Proof. Let G ∼= Cr�Ps, where r,s ≥ 3. By labeling the vertices of the internal and external cycles of G as the vertices of the internal cycle by v1,v2, . . . ,vr and the vertices of external cycle by u1,u2, . . . ,ur see as Figure 2. Let us partition the set of vertices as following subsets: Figure 2. Cr�Ps S1 = {vi, 1 ≤ i ≤ r}. S2 = {ui, 1 ≤ i ≤ r}. S3 = {wj,wj ∈ V (G) and w /∈ (S1 ∪S2)}. By defining a the coloring function, f : V (G) −→{1, 2, . . . ,r(s− 1)} such that: for any vertex x f(x) =   i, if x = vi or x = ui; j + r, if wj ∈ S3. Obviously, f is a monotone r(s− 1) coloring function. So χmo(G) ≤ r(s− 1). (3.3) The set S1 ∪S3 is monotone clique set with r(s− 1) vertices. Therefore, χmo(G) ≥ r(s− 1). (3.4) Int. J. Anal. Appl. 18 (6) (2020) 1120 Hence by inequalities 3.3 and 3.4, we get, χmo(G) = r(s− 1). � The stacked book is defined as the graph which construct by Cartesian product between star Sr of r + 1 vertices and path Ps of s vertices and denoted by Br,s. That means Br,s ∼= Sr�Ps. Theorem 3.3. For any stacked book graph G ∼= Sr�Ps, where r ≥ 3 and s ≥ 2 χmo(G) =   4, if s = 2;2s− 3, if s ≥ 3. Proof. Let G ∼= Sr�Ps. By labeling the vertices of the graph by using the horizontal lines of the vertices, let the center line L0 and the outside lines are L1,L2, . . . ,Lr. By labeling the vertices of lines from the left to the right according to the line, the vertices on the center line means the vertices on the line L0 are labeling as v01,v02, . . . ,v0s, the vertices on the line L1 are labeling as v11,v12, . . . ,v1s, the vertices on the line L2 are labeling as v21,v22, . . . ,v2s and so on till the vertices on the line Lr are labeling as vr1,vr2, . . . ,vrs (See Figure 3). Figure 3. Stacked book graph Let us partition the vertex set of the graph G to following subsets: S1 = {vi1,vis; 1 ≤ i ≤ r}, S2 = {v0j; 1 ≤ j < s}, S3 = {v1j; 2 < j < s}, S4 = {vi2; 1 ≤ i ≤ r}, S5 = {vij; 2 ≤ i ≤ r, and 2 < j < s} and S6 = {v0s}. Define a coloring function f : V (G) −→{1, 2, . . . ,k} such that: Int. J. Anal. Appl. 18 (6) (2020) 1121 f(vij) =   1, if vij ∈ S1 ; j + 1, if vij ∈ S2; s + j − 2, if vij ∈ S3; f(v01), if vij ∈ S4 or vij = v0s ; f(v1j), if vij ∈ S5. Clearly, f is a monotone (2s− 3) coloring function. So χmo(G) ≤ (2s− 3). (3.5) The set S2∪S3∪{v11} is monotone clique set in G and need (2s−3) colors for monotone coloring. Therefore, χmo(G) ≥ (2s− 3). (3.6) Hence by inequalities 3.5 and 3.6, we get, χmo(G) = (2s− 3). � Lemma 3.1. Let G and H be any non trivial connected graphs and G�H is the Cartesian product. Then any two vertices (u,v) and (x,y) are monotone adjacent in G�H, if one of the following satisfy: (1) x = u in G and y is monotone adjacent with v in H. (2) x and u are monotone adjacent vertices in G and y = v in H. (3) x is monotone adjacent with u in G and y is monotone adjacent with v in H. Theorem 3.4. For any two graphs G and H, χmo(G) + χmo(H) − 1 ≤ χmo(G�H) ≤ χmo(G)χmo(H). Proof. Let χmo(G) = k1 and χmo(H) = k2. By Theorem 2.3, ωmo(G) = k1 and ωmo(H) = k2. Then there exist two monotone cliques: C1 = {u1,u2, . . . ,uk1} and C2 = {v1,v2, . . . ,vk2} in G and H respectively, with k1 and k2 vertices. Therefore, {(u1,v1), (u2,v1), (u3,v1), . . . , (uk1,v1), (uk1,v2), (uk1,v3), . . . , (uk1,vk3 )} is monotone clique in G�H with k1 + k2 − 1 vertices.Therefore, k1 + k2 − 1 ≤ ωmo(G�H) = χmo(G�H). Then, ωmo(G) + ωmo(H) − 1 ≤ χmo(G�H) (3.7) Now, assume that χmo(G�H) = m, that means ωmo(G�H) = m, then there exists at least one monotone clique set with m vertices, say C = {w1,w2, . . . ,wm}. By definition of Cartesian product any two adjacent Int. J. Anal. Appl. 18 (6) (2020) 1122 vertices wi = (ai,bi),wi+1 = (ai+1,bi+1) either aiai+1 is connected in G with bi = bi+1 or bibi+1 is connected in H with ai = ai+1. Any sequence of adjacent vertices on C which they are mutually different in first component will make correspondence monotone clique in G. Similarly, any sequence of adjacent vertices which they are mutually different in second component will make correspondence monotone clique in H. Let the maximum number of vertices for the correspondence monotone clique in G which correspondence vertices in G�H is s and similarly, the maximum number of vertices for the correspondence monotone clique in H which correspondence vertices in G�H is t. Then the number of vertices on C = {w1,w2, . . . ,wm} will be at most m = st, since s ≤ ωmo(G) and t ≤ ωmo(H). Then ωmo(G�H) ≤ ωmo(G)ωmo(H) (3.8) Thus, by inequalities 3.7 and 3.8, χmo(G) + χmo(H) − 1 ≤ χmo(G�H) ≤ χmo(G)χmo(H). � Conflicts of Interest: The author(s) declare that there are no conflicts of interest regarding the publication of this paper. References [1] D.M. Cardoso, J.O. Cerdeira, J.P. Cruz, C. Dominic, Injective Edge Chromatic Index of a Graph, ArXiv:1510.02626 [Math]. (2015). [2] J.L. Fouquet , J.L. Jolivet, Strong edge-colorings of graphs and applications to multi k -gons, Ars Combin. 16A (1983), 141-150. [3] F. Guthrie. Note on the colouring of maps. Proc. R. Soc. Edinburgh. 10 (1880), 727–728. [4] I. Gutman, Kragujevac trees and their energy, Sci. Publ. State Univ. Novi Pazar Ser. A., Appl. Math. Inform. Mech. 6 (2) (2014), 71-79. [5] G. Hahn, J. Kratochv́il, J. s̆irán̆ and D. Sotteau, On the injective chromatic number of graphs. Discrete Math. 256 (2002), 179–192. [6] F. Harary, Graph theory, Addison-Wesley, Reading Mass. (1969). [7] J.X. Li, J.M. Guo, W.C. Shiu, On the second largest Laplacian eigenvalues of graphs, Linear Algebra Appl. 438 (2013), 2438–2446. [8] N. Zufferey, P. Amstutz, P. Giaccari, Graph colouring approaches for a satellite range scheduling problem, J. Schedul. 11 (4) (2008), 263–277. 1. Introduction 2. Monotone Chromatic Number of Graphs 3. Monotone Chromatic number for Some Cartesian Product of Graphs References