American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 © Global Society of Scientific Research and Researchers http://asrjetsjournal.org/ On Chromatic Number and Edge-Chromatic Number of the Ottomar Graph Mark Caay a*, Esperanza Arugay b a Convergys Philippines, Apas, Cebu City, 6000 , Philippines b Department of Mathematics, College of Science and Mathematics, Mindanao State University – Iligan Institute of Technology, Tibanga, Iligan City, 9200, Philippines aEmail: markycaay126@yahoo.com bEmail: adamandeba@yahoo.com Abstract The path graph Pn, consists of the vertex set V = {1,2, … , n} and the edge set E = �{1,2}, {2,3}, . . . , {n − 1, n}�. The cycle graph Cn, is the path graph, Pn with an additional edge {1, n}. Define the Ottomar Graph, denoted by On,m, to be the graph Cn, n ϵℤ+, n ≥ 3, with a vertex connected by a path P2 to a vertex of Cm, m ϵ ℤ+, n ≥ 3. Cn is called the heart while Cm is called a foot (feet for plural). Note that there are n copies of Cm. The chromatic number of a graph G, denoted by χ(G), is the minimum number of colors the vertices of G maybe colored such that any two adjacent vertices have different colors. The edge-chromatic number of a graph G, denoted by χe(G), is the minimum number of colors the edges of G maybe colored such that any two incident edges have different colors. The chromatic number and the edge-chromatic number of the ottomar graph are determined. When will the two invariants be equal or when will they be unequal? When the connecting path Pk has order greater than 2, what happens to the value of χ(G) and χe(G)? Also in the paper, the other coloring invariants are compared and investigated with chromatic number and edge-chromatic number. Keywords: path; cycle; chromatic number; edge-chromatic number; ottomar graph; generalized ottomar graph. 1. Introduction A pair 𝐺 = (𝑉,𝐸) with 𝐸 ⊆ 𝐸(𝑉) is called a graph (on 𝑉). The elements of 𝑉 are the vertices of 𝐺, and those of 𝐸 the edges of 𝐺. ------------------------------------------------------------------------ *Corresponding author 98 http://asrjetsjournal.org/ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 The vertex set of a graph 𝐺 is denoted by 𝑉𝐺 and its edge set by 𝐸𝐺 . Therefore 𝐺 = (𝑉𝐺 ,𝐸𝐺). The path graph 𝑃𝑛, consists of the vertex set 𝑉 = {1 , 2 , . . . ,𝑛} and the edge set 𝐸 = {{1,2}, {2,3}, . . . , {𝑛 − 1,𝑛}}. The cycle graph 𝐶𝑛, is the path graph, 𝑃𝑛 with an additional edge {1,𝑛}. The chromatic number of a graph 𝐺, denoted by 𝜒(𝐺), is the minimum number of colors the vertices of 𝐺 maybe colored such that any two adjacent vertices have different colors. The edge-chromatic number of a graph 𝐺, denoted by 𝜒𝑒(𝐺), is the minimum number of colors the edges of 𝐺 maybe colored such that any two incident edges have different colors. Known Result 1 [2] If 𝐶𝑛 is a cycle of order 𝑛, then Define the Ottomar Graph, denoted by 𝑂𝑛,𝑚, to be the graph 𝐶𝑛 ,𝑛 𝜖ℤ+,𝑛 ≥ 3, with a vertex connected by a path 𝑃2 to a vertex of 𝐶𝑚,𝑚 𝜖 ℤ+,𝑛 ≥ 3. 𝐶𝑛 is called the heart while 𝐶𝑚 is called a foot (feet for plural). Note that there are 𝑛 copies of 𝐶𝑚. 2. Identities of Chromatic Number and Edge-Chromatic Number of Ottomar Graph Theorem 2.1 For all integers 𝑚,𝑛 ≥ 3,𝜒�𝑂𝑛,𝑚� = 3, if: 99 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 • Case 1: 𝑚,𝑛 are both odd • Case 2: 𝑚 is odd, 𝑛 is even • Case 3: 𝑚 is even, 𝑛 is odd and • 𝜒�𝑂𝑛,𝑚� = 2 if 𝑚,𝑛 are even. Proof: • Case 1: 𝑚 and 𝑛 are both odd If 𝑚,𝑛 are odd, then by equation (1.1), 𝜒(𝐶𝑚) = 𝜒(𝐶𝑚) = 3, thus 𝜒�𝑂𝑛,𝑚� ≠ 2. Suppose the vertices of 𝐶𝑚 and 𝐶𝑛 are colored with the same set of different colors say 𝑎1, 𝑎2, 𝑎3. Then the path 𝑃2 is attached to a vertex colored say 𝑎𝑖 , 𝑖 = 1 , 2, 3 of 𝐶𝑚 and the other end vertex is attached to a vertex colored say 𝑎𝑗 , 𝑗 = 1,2,3 of 𝐶𝑛, where 𝑎𝑖 ≠ 𝑎𝑗. Hence, three is the minimum number of colors to color the vertices of 𝑂𝑛,𝑚, where 𝑚,𝑛 are both odd. Consequently, 𝜒�𝑂𝑛,𝑚� = 3. • Case 2: 𝑚 is odd, 𝑛 is even If 𝑚 is odd and 𝑛 is even, then by equation (1.1), 𝜒(𝐶𝑚) = 3 and 𝜒(𝐶𝑛) = 2, so 𝜒�𝑂𝑛,𝑚� ≠ 2. Suppose that the vertices of 𝐶𝑛 are colored with two of the colors that also color the vertices of 𝐶𝑚 , say 𝑎1, 𝑎2 for 𝐶𝑛 and 𝑎1, 𝑎2, 𝑎3 for 𝐶𝑚. Then a path 𝑃2 is attached to vertex colored say 𝑎𝑖 , 𝑖 = 1,2,3 of 𝐶𝑚 and other end vertex is attached to a vertex colored 𝑎𝑗 , 𝑗 = 1,2 of 𝐶𝑛, where 𝑎𝑖 ≠ 𝑎𝑗. This means that the minimum number of colors to color the vertices of 𝑂𝑛,𝑚, where 𝑛 is even and 𝑚 is odd is three. Thus, 𝜒�𝑂𝑛,𝑚� = 3. • Case 3: 𝑚 is even, 𝑛 is odd Proof of this case is similar to case 2. • Case 4: 𝑚,𝑛 are both even If 𝑚,𝑛 are even then by equation (1.1), 𝜒(𝐶𝑚) = 𝜒(𝐶𝑛) = 2. Suppose the vertices of 𝐶𝑚 and 𝐶𝑛 are colored with the same set of different colors, say 𝑎1, 𝑎2. Then a path 𝑃2 is attached to a vertex colored say 𝑎𝑖 , 𝑖 = 1,2 of 100 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 𝐶𝑚 and the other end vertex is attached to a vertex colored say 𝑎𝑗 , 𝑗 = 1,2 of 𝐶𝑛, where 𝑎𝑖 ≠ 𝑎𝑗. Hence, two is the minimum number of colors to color vertices of 𝑂𝑛,𝑚, where, 𝑛,𝑚 are both even. Consequently, 𝜒�𝑂𝑛,𝑚� = 2. ∎ Theorem 2.2 For all integers 𝑚,𝑛, 𝑚,𝑛 ≥ 3, 𝜒𝑒�𝑂𝑛,𝑚� = 3. Proof: To prove this theorem, we consider the following cases: • Case 1: 𝑚,𝑛 are both odd If 𝑚,𝑛 are both odd, then by equation (1.2), 𝜒𝑒(𝐶𝑚) = 𝜒𝑒(𝐶𝑛) = 3. Thus, 𝜒𝑒�𝑂𝑛,𝑚� ≠ 2 since there exist three incident edges. Suppose the edges of 𝐶𝑚 and 𝐶𝑛 are colored with the same set of different colors, say 𝑏𝑖 , 𝑏𝑗 , 𝑏𝑘. Then a path 𝑃2 connecting 𝐶𝑚 and 𝐶𝑛 must have an edge colored with one of the colors 𝑏1, 𝑏2, 𝑏3, say 𝑏𝑖 , 𝑖 = 1,2,3, where 𝑏𝑖 is incident to edges colored 𝑏𝑗 and 𝑏𝑘 of 𝐶𝑚 and is also incident to edges colored 𝑏𝑗 and 𝑏𝑘 of 𝐶𝑛, 𝑏𝑖 ≠ 𝑏𝑗 ≠ 𝑏𝑘. Hence, three is the minimum number of colors to color the edges of 𝑂𝑛,𝑚, where 𝑛,𝑚 are both odd. Consequently, 𝜒𝑒�𝑂𝑛,𝑚� = 3. • Case 2: 𝑚,𝑛 are both even If 𝑚,𝑛 are both even, then by equation (1.2), 𝜒𝑒(𝐶𝑚) = 𝜒𝑒(𝐶𝑛) = 2. Thus, 𝜒𝑒�𝑂𝑛,𝑚� ≠ 2 since there exist three incident edges. Without a loss of generality, suppose the edges of 𝐶𝑚 and 𝐶𝑛 are colored with same set of different colors 𝑏1, 𝑏2. Then a path 𝑃2 connecting 𝐶𝑚 and 𝐶𝑛 where its edge is incident to colors 𝑏1, 𝑏2 edges of 𝐶𝑚 and 𝐶𝑛, must have an edge colored with 𝑏3 such that 𝑏1 ≠ 𝑏2 ≠ 𝑏3. Hence, three is the minimum number of colors to color the edges of 𝑂𝑛,𝑚, where 𝑚,𝑛 are both even. Consequently, 𝜒𝑒�𝑂𝑛,𝑚� = 3. • Case 3: 𝑚 is odd, 𝑛 is even If 𝑚 is odd, 𝑛 is even, then by equation (1.2), 𝜒𝑒(𝐶𝑚) = 3 and 𝜒𝑒(𝐶𝑛) = 2. Thus 𝜒𝑒�𝑂𝑛,𝑚� ≠ 2. Without a loss of generalization, suppose that the edges of 𝐶𝑛 are colored with two of the colors that also color the edges of 𝐶𝑚, say 𝑏1, 𝑏2 colors of 𝐶𝑛 and 𝑏1, 𝑏2, 𝑏3 colors of 𝐶𝑚. Then a path 𝑃2 connecting 𝐶𝑚 and 𝐶𝑛 must have an edge colored with 𝑏3 and must also be incident to edges colored 𝑏1 and 𝑏2 of 𝐶𝑚 and must also be incident to edges colored 𝑏1 and 𝑏2 of 𝐶𝑛. Hence, three is the minimum number of colors to color the edges of 𝑂𝑛,𝑚, where 𝑚 is odd, 𝑛 is even. Consequently, 𝜒𝑒�𝑂𝑛,𝑚� = 3. • Case 4: 𝑚 is even, 𝑛 is odd If 𝑚 is even, 𝑛 is odd, then the proof of this case is similar to case 3. ∎ Corollary 2.1 101 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 For all integers 𝑚,𝑛 ≥ 3 𝜒�𝑂𝑛,𝑚� ≤ 𝜒𝑒�𝑂𝑛,𝑚� Proof: Note that for the cases where 𝑚,𝑛 are both odd, 𝑚 is odd, 𝑛 is even, and 𝑚 is even, 𝑛 is odd, by Theorem 2.1, 𝜒�𝑂𝑛,𝑚� = 3 and by Theorem 2.2, 𝜒𝑒�𝑂𝑛,𝑚� = 3. Thus, 𝜒�𝑂𝑛,𝑚� ≤ 𝜒𝑒�𝑂𝑛,𝑚�. Similarly, for cases where 𝑚,𝑛 are both even, by Theorem 2.1, 𝜒�𝑂𝑛,𝑚� = 2 and by Theorem 2.2, 𝜒𝑒�𝑂𝑛,𝑚� = 3. Thus, 𝜒�𝑂𝑛,𝑚� ≤ 𝜒𝑒�𝑂𝑛,𝑚�. Therefore, in all cases, 𝜒�𝑂𝑛,𝑚� ≤ 𝜒𝑒�𝑂𝑛,𝑚�. ∎ Remark 2.1 For all integers 𝑘 ≥ 3, 𝜒(𝑃𝑘) = 𝜒𝑒(𝑃𝑘) = 2. 3. Generalized Ottomar Graph Define the Generalized Ottomar Graph, 𝑂𝑘𝑛,𝑚, is graph 𝐶𝑛 ,𝑛 ∈ ℤ+,𝑛 ≥ 3, with each vertex connected by a path 𝑃𝑘 , 𝑘 ∈ ℤ+, 𝑘 ≥ 3 to a vertex of 𝐶𝑚 ,𝑚 ∈ ℤ+,𝑚 ≥ 3. 𝐶𝑛 is called a heart while 𝐶𝑚 is called a foot (feet for plural). Note that there are 𝑛 copies of 𝐶𝑚. Theorem 3.1 For all integers 𝑘 = 3, 4, 𝜒�𝑂𝑘𝑛,𝑚 � = 3 if, • 𝑚,𝑛 are both odd • 𝑚 is odd, 𝑛 is even • 𝑚 is even, 𝑛 is odd and 𝜒�𝑂𝑘𝑛,𝑚 � = 2, 𝑖𝑓 𝑚,𝑛 𝑎𝑟𝑒 𝑏𝑜𝑡ℎ 𝑒𝑣𝑒𝑛. Proof: • Case 1: 𝑚,𝑛 are both odd If 𝑚,𝑛 are both odd, then by equation (1.1), 𝜒(𝐶𝑚) = 𝜒(𝐶𝑛) = 3. Thus, 𝜒�𝑂𝑘𝑛,𝑚 � ≥ 3. Suppose the vertices of 𝐶𝑚 and 𝐶𝑛 are colored with the same set of different colors say 𝑎1, 𝑎2, 𝑎3. Consider the following subcases where 𝑘 = 3 (odd) and 𝑘 = 4 (even): • subcase 1.1: If 𝑘 = 3 Then a path 𝑃3 with vertices colored with two from the same set of different colors 𝑎1, 𝑎2, 𝑎3, is attached to a 102 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 vertex colored say 𝑎𝑖 , 𝑖 = 1,2,3 of 𝐶𝑚 and the other end vertex is also connected to 𝑎𝑖 of 𝐶𝑛 , such that the second (middle) vertex of 𝑃3 is 𝑎𝑗 , 𝑗 = 1,2,3, where 𝑎𝑖 ≠ 𝑎𝑗. Thus three is the minimum number of colors to color the vertices of 𝑂3𝑛,𝑚, where 𝑚,𝑛 are both odd. Consequently, 𝜒�𝑂3 𝑛,𝑚 � = 3. • subcase 1.2: If 𝑘 = 4 Note that by Remark 2.1, 𝜒(𝑃4) = 2. Suppose further that 𝑃4 is colored with two from the same set of different colors that color the vertices of 𝐶𝑚 and 𝐶𝑛, say 𝑎𝑖 , 𝑎𝑗 , 𝑖, 𝑗 = 1,2,3. Then, the first vertex of 𝑃4 is colored 𝑎𝑖 of 𝐶𝑚 and the last vertex of 𝑃4, colored 𝑎𝑗 is attached to 𝑎𝑗 of 𝐶𝑛. The other vertices of 𝑃4 are colored 𝑎𝑖 , 𝑎𝑗 such that no two adjacent vertices have the same color. Thus, three is the minimum number of colors to color the vertices of 𝑂4𝑛,𝑚, where 𝑚,𝑛 are both odd. Consequently, 𝜒�𝑂4 𝑛,𝑚 � = 3. • Case 2: 𝑚 is odd, 𝑛 is even If 𝑚 is odd, 𝑛 is even, then by equation (1.1), 𝜒(𝐶𝑚) = 3 and 𝜒(𝐶𝑛) = 2. Thus, 𝜒�𝑂𝑘𝑛,𝑚 � ≥ 3. Suppose that the vertices of 𝐶𝑛 are colored with two of the different colors that also color the vertices of 𝐶𝑚, say 𝑎𝑖 , 𝑎2 colors for 𝐶𝑛 and 𝑎1, 𝑎2, 𝑎3 colors for 𝐶𝑚. Consider the following subcases where 𝑘 = 3 (odd) and 𝑘 = 4 (even): • subcase 2.1: If 𝑘 = 3 Then a path 𝑃3 is attached to vertex colored say 𝑎𝑖 , 𝑖 = 1 , 2 , 3 of 𝐶𝑚 and the other end vertex is also connected to a vertex colored 𝑎𝑖 of 𝐶𝑛, such that the second (middle) vertex of 𝑃3 is 𝑎𝑗 , 𝑗 = 1 , 2 , 3, where 𝑎𝑖 ≠ 𝑎𝑗. Thus, three is the minimum number of colors to color the vertices of 𝑂3𝑛,𝑚 where 𝑚 is odd and 𝑛 is even. Consequently, 𝜒�𝑂3𝑛,𝑚 � = 3. • subcase 2.2: If 𝑘 = 4 Note that by Remark 2.1, 𝜒(𝑃4) = 2. Suppose further that 𝑃4 is colored with two from the same set of different colors that color the vertices of 𝐶𝑚 and 𝐶𝑛, say 𝑎1, 𝑎2. Then, the first vertex of 𝑃4 is attached to a vertex colored 𝑎𝑖 , 𝑖 = 1,2 of 𝐶𝑚 and is adjacent to a vertex colored 𝑎𝑗 , 𝑗 = 1,2, which is the second vertex of 𝑃4, and the last vertex is then connected to a vertex colored 𝑎𝑗 , 𝑗 = 1,2 of 𝐶𝑛, where 𝑎𝑖 ≠ 𝑎𝑗. Note that the vertices of 𝐶𝑚 are colored {𝑎1, 𝑎2, 𝑎3}. Thus, three is the minimum number of colors to color the vertices of 𝑂4𝑛,𝑚, where 𝑚 is odd, 𝑛 is even. Consequently, 𝜒�𝑂4 𝑛,𝑚 � = 3. • Case 3: 𝑚 is even, 𝑛 is odd If 𝑚 is even, 𝑛 is odd, then the proof of this case is similar to case 2. • Case 4: 𝑚,𝑛 are both even If 𝑚,𝑛 are both even, then by equation (1.1), 𝜒(𝐶𝑚) = 𝜒(𝐶𝑛) = 2. Suppose the vertices of 𝐶𝑚 and 𝐶𝑛 are 103 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 colored with the same set of different colors say 𝑎1, 𝑎2. Consider the following subcases where 𝑘 = 3 (odd) and 𝑘 = 4 (even): • subcase 4.1: If 𝑘 = 3 Then a path 𝑃3 with vertices colored with the same set of different colors 𝑎1, 𝑎2, is attached to vertex colored say 𝑎𝑖 , 𝑖 = 1 , 2 , 3 of 𝐶𝑚 and the other end vertex is also connected to a vertex colored 𝑎𝑖 of 𝐶𝑛, such that the second (middle) vertex of 𝑃3 is 𝑎𝑗 , 𝑗 = 1 , 2 , 3, where 𝑎𝑖 ≠ 𝑎𝑗. Thus, two is the minimum number of colors to color the vertices of 𝑂3𝑛,𝑚 where 𝑚 is odd and 𝑛 is even. Consequently, 𝜒�𝑂3𝑛,𝑚 � = 2. • subcase 4.2: If 𝑘 = 4 Note that by Remark 2.1, 𝜒(𝑃4) = 2. Suppose further that 𝑃4 is colored with two from the same set of different colors that color the vertices of 𝐶𝑚 and 𝐶𝑛, say 𝑎1, 𝑎2. Then, the first vertex of 𝑃4 is attached to a vertex colored 𝑎𝑖 , 𝑖 = 1,2 of 𝐶𝑚 and is adjacent to a vertex colored 𝑎𝑗 , 𝑗 = 1,2, which is the second vertex of 𝑃4, and the second vertex is adjacent to a vertex colored 𝑎𝑖 , 𝑖 = 1,2, which is the third vertex of 𝑃4, and the last vertex is then connected to a vertex colored 𝑎𝑗 , 𝑗 = 1,2 of 𝐶𝑛, where 𝑎𝑖 ≠ 𝑎𝑗 . Thus, two is the minimum number of colors to color the vertices of 𝑂4𝑛,𝑚, where 𝑚 is odd, 𝑛 is even. Consequently, 𝜒�𝑂4𝑛,𝑚 � = 2. ∎ It is easy to prove that the next corollaries hold. Proofs are similar to Theorem 3.1. Corollary 3.1 For all integers 𝑘 ≥ 3, 𝑘 is odd, 𝜒�𝑂𝑘𝑛,𝑚 � = 3 𝑖𝑓: • 𝑚,𝑛 are both odd • 𝑚 is odd, 𝑛 is even • 𝑚 is even, 𝑛 is odd and 𝜒�𝑂𝑘𝑛,𝑚 � = 2 𝑖𝑓 𝑚,𝑛 𝑎𝑟𝑒 𝑏𝑜𝑡ℎ 𝑒𝑣𝑒𝑛. Corollary 3.2 For all integers 𝑘 ≥ 2, 𝑘 is even, 𝜒�𝑂𝑘𝑛,𝑚 � = 2. Theorem 3.2 For all integers 𝑚,𝑛 ≥ 3 and for integers 𝑘 = 3, 4, 𝜒𝑒�𝑂𝑘𝑛,𝑚 � = 3. 104 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 Proof: • Case 1: 𝑚,𝑛 are both odd If 𝑚,𝑛 are both odd, then by equation (1.2), 𝜒𝑒(𝐶𝑚) = 𝜒𝑒(𝐶𝑛) = 3. Thus, 𝜒𝑒�𝑂𝑘𝑛,𝑚 � ≥ 3. Suppose the edges of 𝐶𝑚 and 𝐶𝑛 are colored with the same set of different colors, say 𝑏1, 𝑏2, 𝑏3. • subcase 1.1: If 𝑘 = 3 Note that 𝑃3 has two edges and suppose we color its edges with two from the set of different colors that color the edges of 𝐶𝑚 and 𝐶𝑛, say 𝑏𝑖 , 𝑏𝑗. Then 𝑏𝑖 color of 𝑃3 is attached to 𝐶𝑚 and is incident to edges colored 𝑏𝑗 and 𝑏𝑘 of 𝐶𝑚, while the other color of the edge of 𝑃3 say 𝑏𝑗 is attached to 𝐶𝑛 and is incident to edges colored 𝑏𝑖 and 𝑏𝑘 of 𝐶𝑛, where 𝑏𝑖 ≠ 𝑏𝑗 ≠ 𝑏𝑘. Hence, three is the minimum number of colors that color the edges of 𝑂3𝑛,𝑚. Consequently, 𝜒𝑒�𝑂3𝑛,𝑚 � = 3. • subcase 2.1: If 𝑘 = 4 Note that by Remark 3.1, 𝜒𝑒(𝑃4 ) = 2 and suppose the edges of 𝑃4 are colored with two from the same set of different colors that color the edges of 𝐶𝑚 and 𝐶𝑛 , say 𝑏𝑖 , 𝑏𝑗 . Since 𝑃4 has three edges, suppose that 𝑃4 is colored with 𝑏𝑖′𝑠 and 𝑏𝑗 , 𝑖 = 1,2,3, 𝑗 = 1,2,3 such that 𝑏𝑗 is the middle edge and the two 𝑏𝑖′𝑠 are first and the last edges. Then, 𝑏𝑖 of 𝑃4 is connected to 𝐶𝑚 and is incident to edges colored 𝑏𝑗 and 𝑏𝑘 of 𝐶𝑚, while the other 𝑏𝑖 of 𝐶𝑛 . Hence, three is the minimum number of colors that color the edges of 𝑂4𝑛,𝑚 . Consequently, 𝜒𝑒�𝑂4𝑛,𝑚 � = 3. • Case 2: 𝑚 is odd, 𝑛 is even If 𝑚 is odd, 𝑛 is even, then by equation (1.2), 𝜒𝑒(𝐶𝑚 ) = 3 and 𝜒𝑒(𝐶𝑛 ) = 2. Suppose the edges of 𝐶𝑛 are colored with two from the same set of different colors that color the edges of 𝐶𝑚, say 𝑏1, 𝑏2 for 𝐶𝑛 and 𝑏1, 𝑏2, 𝑏3 for 𝐶𝑚. By this, the entire proof follows from case 1. • Case 3: 𝑚 is even, 𝑛 is odd If 𝑚 is even, 𝑛 is odd, then the proof of this case is similar to case 2. • Case 4: 𝑚,𝑛 are both even If 𝑚,𝑛 are both even, then by equation (1.2), 𝜒𝑒(𝐶𝑚 ) = 𝜒𝑒(𝐶𝑛 ) = 2. Suppose the edges of 𝐶𝑚 are colored by a set of different colors say 𝑏𝑗 , 𝑏𝑘 and 𝐶𝑛 is colored with the set of different colors, say 𝑏𝑖 , 𝑏𝑘, where 𝑖, 𝑗 , 𝑘 = 1 , 2 , 3 and 𝑏𝑖 ≠ 𝑏𝑗 ≠ 𝑏𝑘. • subcase 4.1: If 𝑘 = 3 105 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 Note that by Remark 2.1, 𝜒𝑒(𝑃3 ) = 2. Clearly, 𝜒𝑒�𝑂3𝑛,𝑚 � ≥ 3 since 𝑂3𝑛,𝑚 has three edges incident to each other at the endpoints of 𝑃3. Then 𝑏𝑖 color of 𝑃3 is attached to 𝐶𝑚 and is incident to edges colored 𝑏𝑗 and 𝑏𝑘 of 𝐶𝑚, while the other color of the edge of 𝑃3 say 𝑏𝑗 is attached to 𝐶𝑛 and is incident to edges colored 𝑏𝑖 and 𝑏𝑘 of 𝐶𝑛 and is incident to edges colored 𝑏𝑖 and 𝑏𝑘 of 𝐶𝑛, where 𝑏𝑖 ≠ 𝑏𝑗 ≠ 𝑏𝑘. Hence, three is the minimum number of colors that color the edges of 𝑂3𝑛,𝑚. Consequently, 𝜒𝑒�𝑂3𝑛,𝑚 � = 3. • subcase 4.2: If 𝑘 = 4 Note that 𝑃4 has three edges and by Remark 3.1, 𝜒𝑒(𝑃4 ) = 2. Clearly, 𝜒𝑒�𝑂4𝑛,𝑚 � ≥ 3 since 𝑂4𝑛,𝑚 has three edges incident to each other at the endpoints of 𝑃𝑘. Suppose that there are two 𝑏𝑖′𝑠, 𝑖 = 1 , 2 , 3 and one 𝑏𝑗 , 𝑗 = 1 , 2 , 3 is the color of the middle edge, while the two 𝑏𝑖′𝑠, 𝑖 = 1 , 2 , 3 are the colors of the first and the last edges. Then the first 𝑏𝑖 color is attached to 𝐶𝑚 and is incident to edges colored 𝑏𝑗 and 𝑏𝑘 colors 𝐶𝑚, while the other 𝑏𝑖 is connected to 𝐶𝑛 and is also incident to edges 𝑏𝑗 and 𝑏𝑘 colors of 𝐶𝑛. Hence, three is the minimum number of colors that color the edges of 𝑂4𝑛,𝑚. Consequently, 𝜒𝑒�𝑂4𝑛,𝑚 � = 3. Therefore for any cases, the proof follows. Similar arguments will hold for the last Theorem. Theorem 3.3 For all integers m, n ≥ 3, and for all integers k ≥ 3, χe�Ok n,m � = 3. Corollary 3.3 For all integers m, n ≥ 3 and for any integers k ≥ 3, 𝜒�𝑂𝑘 𝑛,𝑚 � ≤ 𝜒𝑒�𝑂𝑘𝑛,𝑚 � ≤ 3. Proof: Note that for cases where 𝑚,𝑛 are both odd, 𝑚 is odd, 𝑛 is even and 𝑚 is even, 𝑛 is odd, by Theorem 3.1, 𝜒�𝑂𝑘 𝑛,𝑚 � = 3 and by Theorem 3.2, 𝜒𝑒�𝑂𝑘𝑛,𝑚 � = 3. Thus, 𝜒�𝑂𝑘𝑛,𝑚 � ≤ 𝜒𝑒�𝑂𝑘𝑛,𝑚 � . Similarly, for cases where 𝑚,𝑛 are both even, by Theorem 3.1, 𝜒�𝑂𝑘𝑛,𝑚 � = 2 and by Theorem 3.2, 𝜒𝑒�𝑂𝑘𝑛,𝑚 � = 3. Thus, 𝜒�𝑂𝑘𝑛,𝑚 � ≤ 𝜒𝑒�𝑂𝑘𝑛,𝑚 �. Therefore, in all cases, 𝜒�𝑂𝑘𝑛,𝑚 � ≤ 𝜒𝑒�𝑂𝑘𝑛,𝑚 �. Acknowledgements The authors would like to thank the referee for the helpful suggestions and the members of ASRJETS. Special thanks to authors’ families and friends. References [1]. E. Arugay. “Path Chromatic Number of a Graph.” In Dissertation Conference. Ateneo de Manila University, 1990. 106 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 16, No 1, pp 98-107 [2]. R. Balakrishnan and K. Ranganathan. A Textbook of Graph Theory, 2nd Ed., Springer, 2012. [3]. T. Harju. Lecture Notes on GRAPH THEORY. Department of Mathematics, University of Turku, FIN-20014, Turku, Finland, 2012. 107