EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 4, 2022, 1822-1835 ISSN 1307-5543 – ejpam.com Published by New York Business Global Acyclic and Star Coloring of Powers of Paths and Cycles Ali Etawi1,∗, Manal Ghanem1, Hasan Al-Ezeh1 1 Mathematics, The University of Jordan, Amman, Jordan Abstract. Let G = (V,E) be a graph. The kth− power of G denoted by Gk is the graph whose vertex set is V and in which two vertices are adjacent if and only if their distance in G is at most k. A vertex coloring of G is acyclic if each bichromatic subgraph is a forest. A star coloring of G is an acyclic coloring in which each bichromatic subgraph is a star forest. The minimum number of colors such that G admits an acyclic (star) coloring is called the acyclic (star) chromatic number of G and is denoted by χa(G)(χs(G)). In this paper we prove that for n ≥ k + 1, χs(P k n ) = min{⌊k+n+1 2 ⌋, 2k + 1} and χa(P k n ) = k + 1. Further, we show that for n ≥ (k + 1)2, 2k+1 ≤ χs(C k n) ≤ 2k+2 and k+2 ≤ χa(C k n) ≤ k+3. Finally, we derive the formula χa(C k n) = k+2 for n ≥ (k + 1)3. 2020 Mathematics Subject Classifications: 05C15, 05C38 Key Words and Phrases: Acyclic Coloring, Powers of Cycles, Powers of Paths, Star Coloring 1. Introduction Graph Theory is widely used in many areas such as the study of molecules and con- struction of bonds in chemistry, operations research, modeling transport networks, activity networks, computational biochemistry, map coloring, and GSM mobile phone networks, and others [8]. Graph coloring is a branch of graph theory that deals with such applica- tions. Coloring of a graph is an assignment of colors to the elements like vertices, edges, or faces (regions) of a graph. A coloring is called proper coloring if no two adjacent ele- ments are assigned the same color. The most common types of graph colorings are vertex coloring, edge coloring, and face coloring. A k− coloring of a graph G = (V (G), E(G)) is a function c : V (G) → {1, 2, ..., k}. An acyclic coloring of a graph G is a proper coloring such that all induced bicolored subgraphs of G contain no cycles, in other words, every two color classes induce a forest. Star coloring is acyclic coloring where every bicolored subgraph induces a star forest. The chromatic number of G, denoted χ(G), is the mini- mum α such that G admits a k−proper coloring; the acyclic chromatic number of a graph G, denoted χa(G), is the minimum number k such that G admits a k − acyclic coloring; ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i4.4574 Email addresses: etawi 1412@yahoo.com (A. Etawi), m.ghanem@ju.edu.jo (M. Ghanem) https://www.ejpam.com 1822 © 2022 EJPAM All rights reserved. A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1823 and the star chromatic number of a graph G, denoted χs(G), is the minimum number k such that G admits a k − star coloring. All graphs considered in this article are finite undirected and simple (no loops or multiple edges). All coloring considered in this article is vertex coloring. The following is an obvious observation that we use in our work. Observation: For a proper coloring c of a graph G the following hold: (1) c is an acyclic coloring of G if and only if every cycle in G admits at least three colors. (2) c is a star coloring of G if and only if every path on four vertices in G admits at least three colors. Acyclic and star coloring were introduced in the early seventies by Grünbaum [3]. Grünbaum showed that a graph with a maximum degree 3 has 4− acyclic colorings. Burnstein [2] proved that a graph with a maximum degree 4 has 5 − acyclic colorings. Wood [10] studied the star and acyclic chromatic numbers of subdivision graph G′ of a graph G. A great deal of research has been conducted since then. Recently, Wang et al. [9] studied the acyclic choosability of graphs with bounded degrees. Acyclic and star coloring problems are specialized vertex coloring problems that arise in the efficient computation of Hessians using automatic differentiation or finite differencing when both sparsity and symmetry are exploited. The kth power of a graph G is defined on the same set of vertices as G and has an edge between any pair of vertices of distance at most k in G. The problem of the coloring of squares of graphs has applications to frequency allocation. Transceivers in a radio network communicate using channels at given radio frequencies. Graph coloring formalizes this problem. When the constraint is that nearby pairs of transceivers cannot use the same channel due to interference. However, if two transceivers are using the same channel and both are adjacent to a third station, a clashing of signals is experienced at that third station. This can be avoided by additionally requiring all neighbors of a node to be assigned different colors, i.e., that vertices of distance at most 2 receive different colors. This is equivalent to coloring the square of the underlying network. We attempt here to contribute to both of these perspectives, graph powers and acyclic (star) colorings. We focus on the powers of paths and cycles. As usual, Pn denotes the path on n vertices; and Cn denotes the cycle on n vertices. Acyclic colorings are hereditary in the sense that the restriction of an acyclic coloring to a subgraph is an acyclic coloring. Thus, the acyclic chromatic number is nondecreasing from subgraph to supergraph. The main purpose of this article is to bound and determine the star and acyclic chromatic numbers of powers of paths and cycles. We prove that for large graph sizes, the star and acyclic chromatic numbers of powers of paths and cycles tend to have exact formulas in terms of the power k. As a consequence, we find the value of χa(P k n ) and A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1824 χs(P k n ) in terms of k, we give an upper bound and a sharp lower bound of χa(C k n) in terms of k when (k + 1)2 ≤ n < (k + 1)3. We derived the exact value of χa(C k n) in terms of k for n ≥ (k + 1)3. Additionally, we give an upper bound and sharp lower bound χs(C k n) in terms of k for (k + 1)2 ≤ n. The underlying common technique is the exploitation of the structure of bicolored induced subgraphs, the bounds that we reach in this article are tight with intervals of two values only. Our results are summarized below, [Bold] bounds are sharp. Graph G Range of n χs(G) χa(G) P k n 1 ≤ n ≤ k + 1 n n k + 2 ≤ n ≤ 3k + 1 ⌊k+n+1 2 ⌋ k+1 n ≥ 3k + 1 2k+1 Ck n 1 ≤ n ≤ 2k + 1 n n 2k + 2 ≤ n < (k + 1)2 k+2 ≤ χs(G) ≤ n k + 2 ≤ χa(G) ≤ n (k + 1)2 ≤ n < (k + 1)3 k+2 ≤ χa(G) ≤ k + 3 n ≥ (k + 1)3 2k+1 ≤ χs(G) ≤ 2k + 2 k+2 2. Acyclic Coloring of P k n Let P k n denote the path of order n with vertex set V (P k n ) = {v0, v1, ..., vn−1} and edge set E(P k n )={vivj : 1 ≤ |i− j| ≤ k}. Clearly, P k n is a complete graph when n ≤ k + 1 and hence χa(P k n ) = n. Example 1. In Figure 1 (a), P 2 8 admits an acyclic coloring as shown, the induced subgraph over the vertices colored by the color classes {a, b} is P6, which is not a star. a v1 b v2 c v3 a v4 b v5 c v6 a v7 b v8 (a) Acyclic coloring of P 2 8 1 2 4 5 7 8 (b) The induced subgraph over the color classes {a,b} Figure 1: Acyclic Coloring but not Star Coloring Obviously, every star coloring is acyclic coloring while the converse need not be true in general. A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1825 In this section we calculate the acyclic chromatic number as well as the star chromatic number of P k n . Definition 1. Chordless cycles: A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. Definition 2. Chordal graph: A chordal graph is a graph in which all cycles of four or more vertices have a chord. Proposition 1. ([1]). For every chordal graph G, χa(G) = χ(G). In the following theorem, we will determine χa(P k n ) for n ≥ k + 2. Theorem 1. For n ≥ k + 2, χa(P k n ) = k + 1. Proof. Observing that for k ≥ 3, P k n contains no cordless cycle, and so by Proposition 1 we have χa(P k n ) = χ(P k n ) = k + 1. 3. Star Coloring of P k n In this section, we divide the vertices of paths Pn into three partitions Prefix, Main and Suffix. By that, we were able to determine the value of star chromatic number of P k n . Lemma 1. For n ≥ k + 1, χs(P k n ) ≤ min{2k + 1, ⌊n+k+1 2 ⌋}. Proof. Define c : V (P k n ) → {c0, c1, ..., c2k} by c(vj) = cj mod (2k+1). If va − vb − vc − vd is a bicolored path in P k n , then 2k + 1 = dPn(va, vc) ≤ dPn(va, vb) + dPn(vb, vc) ≤ 2k, a contradiction. So χs(P k n ) ≤ 2k + 1.Clearly, χs(P k n ) = n ≤ ⌊n+k+1 2 ⌋ for n = k + 1. And χs(P k n ) ≤ 2k+1 ≤ ⌊n+k+1 2 ⌋ for n ≥ 3k+2. Now for k+1 < n ≤ 3k+1 we have two cases: Case 1. n = k + (2i+ 1) for 1 ≤ i ≤ k. Then χs(P k n ) ≤ k + i+ 1 = ⌊k+n+1 2 ⌋. To see that, define the (k + i + 1)− proper coloring c : V (P k n ) → {c0, c1, ..., ck+i} by c(vj) = cj mod(k+i+1), and suppose that va − vb − vc − vd is a bicolored path in P k n where a < b < c < d, then dPn (va, vd) = dPn (va, vc) + dPn(vb, vd)− dPn(vb, vc) ≤ k + 2i = n− 1. So, dpn (vb, vc) ≥ k + 2, a contradiction. Case 2. n = k + (2i) for 1 ≤ i ≤ k. Then χs(P k n ) ≤ k + i = ⌊k+n+1 2 ⌋. To see that, define the (k + i)− proper coloring c : V (P k n ) → {c0, c1, ..., ck+i−1} by c(vj) = cj mod(k+i), and suppose that va − vb − vc − vd is a bicolored path in P k n . Since dPn(va, vd) = dPn(va, vc)+dPn(vb, vd)−dPn(vb, vc) ≤ k+2i−1, we have dPn(vb, vc) ≥ k+1, a contradiction. A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1826 Lemma 2. For n = k + 2i+ 1 where 0 ≤ i ≤ k, χs(P k n ) ≥ k + i+ 1. Proof. Let Pn denote the path of order n with V (Pn) = {pi, pi−1, ..., p2, p1,v1,v2, ...,vk+1, s1, s2, ..., si}, and edge set E(Pn) = {pxpx+1 : x = 1, 2, ..., i− 1}∪{vxvx+1 : x = 1, 2, ..., k}∪{sxsx+1 : x = 1, 2, ..., i− 1}∪{p1v1, vk+1s1}. Define three induced cliques of P k n , Prefix (Pr(P k n )), Main (Ma(P k n )) and Suffix (Su(P k n )) with vertex sets V (Pr(P k n )) = {p1, p2, ..., pi}, V (Ma(P k n )) = {v1, v2, ..., vk+1} and V (Su(P k n )) = {s1, s2, ..., si}. Let M = {m1,m2, ...,mk+1} and N = {n1, n2, ..., ni−1} be two disjoint sets of colors, and let c : V (P k n ) → M ∪N be a (k + i) − proper coloring with c(vα) = mα. Then c(Pr(P k n )) ∩M ̸= ϕ and c(Su(P k n )) ∩M ̸= ϕ. Let j and h be the least indices where c(pj) = mx and c(sh) = my for some x, y ∈ {1, 2, ..., k + 1}. Then dPn(pj , vx), dPn(vy, sh) ≥ k + 1, and hence x ≥ k − j + 2, y ≤ h. Claim (1) h > i− j + 1. Let x, y ∈ {1, 2, ..., k + 1} where c(pj) = mx. Suppose that there exists l ≤ i − j + 1 such that c(sl) = my, then k + 1 ≤ dpn(vy, sl) = k + 1 − y + l and hence y ≤ l. But dpn(pj , vy) = j+y−1 ≤ j+ l−1 ≤ i and dpn(vx, sl) = k+1−x+ l ≤ i, so pj−vy−vx−sl is a bicolored path in P k n . Hence c(sl) ∈ N for all l = 1, 2, ..., i− j + 1. Claim (2) If A = {c(p1), c(p2), ..., c(pj−1)} and B = {c(s1), c(s2), ..., c(sh−1)}, then A ∩B has at most h− i+ j − 2 distinct colors. Let t = h− (i− j + 1). If i+ t < k, then h+j−1 ≤ k, so y+j−1 ≤ k. Since dpn(pj , vy) = j+y−1 ≤ j+h−1 ≤ j+(k−j+1)−1 = k and dpn(vx, sh) = (k + 1− x) + h ≤ (k + 1− (k − j + 2)) + (t+ i− j + 1) = t+ i < k, we have a bicolored path pj − vy − vx − sh in P k n . So i+ t ≥ k. Now suppose that x ≥ i + t + 2 − j and y ≤ k + 1 − j, then pj − vy − vx − sh is a bicolored path in P k n . Since x ≥ k − j + 2 and y ≤ h = t + i − j + 1, either x or y ∈ {k + 2− j, k + 3− j, ..., i+ t+ 1− j}. Case 1. k + 2− j ≤ y ≤ i+ t+ 1− j. Let y = k + 2 − j + w for 0 ≤ w ≤ i + t − k − 1 and let w1 ∈ {1, 2, ..., j − 1}, w2 ∈ {1, 2, ..., h − 1}. Clearly, c(pw1), c(sw2) ∈ N. If there exist pw1 , sw2 adjacent to vy such that c(pw1) = c(sw2), then pw1 − vy − sw2 − sh is a bicolored path in P k n . Therefore, c(pw1) ̸= c(sw2) when pw1 and sw2 are adjacent to vy. Let |A ∩ B| = t + α for some integer α. If a is the number of vertices in Pr(P k n ) that are adjacent to vy, then dPn(vy, pa) = a + y − 1 = a + (k + 2 − j + w) − 1 = k, and thus a = j−w− 1. So there exist w = j− 1−a vertices that are colored from the set A and are not adjacent to vy. Therefore, there exist at least (t + α) − w vertices from Pr(P k n ) that are adjacent to vy and colored using colors from A ∩B. Also, if b is the number of vertices in Su(P k n ) that are adjacent to vy, then k = dPn(vy, sb). So, b = k − j + 1 + w, and thus the number of vertices in Su(P k n ) colored from the set B and are not adjacent to vy is (h − 1) − b = t + i − k − 1 − w. Then there exist at least (t + α) − (t + i − k − w − 1) = α + k + w + 1 − i vertices from Su(P k n ) that are adjacent to vy and colored from A ∩ B. Hence the total number of distinct colors is greater than or equal (α + k + 1 + w − i) + (t + α − w) = t + 2α + (k − i) + 1 ≥ 1 + t + 2α, but, 1 + t+ 2α ≤ |(A ∩B)| = t+ α yields to α ≤ −1. Case 2. x ≤ i+ t+ 1− j A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1827 If we mimic the proof of case (1), we get |A∩B| ≤ t− 1.So the number of distinct colors to color Su(P k n ) and Pr(P k n ) from N is |A|+ |B| − |A∩B| ≥ (j− 1)+ (h− 1)− (t− 1) = i colors. Therefore, for n = k + 2i+ 1, χs(P k n ) ≥ k + i+ 1. Example 2. Figure 2 shows an example of the cases in Lemma 2. Let M = {k+2− j, i+ t+ 1− j}. p3 p2 p1 1 v1 2 v2 3 v3 4 v4 s1 s2 s3 Case j h A B Path p3 p2 p1 1 v1 2 v2 3 v3 4 v4 s1 s2 s3 Case j h A B Path p3 p2 p1 1 v1 2 v2 3 v3 4 v4 s1 s2 s3 Case j h A B Path p3 p2 p1 1 v1 2 v2 3 v3 4 v4 s1 s2 s3 Case j h A B Path Prefix Main Suffix Graph Parameters: n = 10 k = 3 i = 3 t = h− i+ j − 1 j is the smallest index in Prefix such that v(pj) ∈ m, c(pj) = c(vx) A = {c(p1), c(p2), ..., c(pj−1)} h is the smallest index in Suffix such that v(sh) ∈ m, c(sh) = c(vy) B = {c(s1), c(s2), ..., c(sh−1)} (a) h ≤ i− j + 1 = 2 2 2 p1 s1 p2 − v1 − v3 − s2 3 1 (b)x > i+ t+ 1− j = 3 y < k + 2− j = 3 2 3 p1 s1,s2 p2 − v2 − v4 − s3 4 2 (c) |A ∩ B| > h − i + j − 2 |A ∩ B| > 1 and y = 3 3 3 p1,p2 s1,s2 p1 − v3 − s2 − s3 4 6 5 6 5 3 (d) |A ∩ B| > h − i + j − 2 |A ∩ B| > 1 and x = 3 3 3 p1,p2 s1,s2 p3 − p1 − v3 − s3 3 6 5 6 5 1 Figure 2: Cases of star coloring P 3 10 Lemma 3. For n = k + 2i where 1 ≤ i ≤ k, χs(P k n ) ≥ k + i. Proof. Let n1 = n − 1. Then χs(P k n1 ) ≤ χs(P k n ) since P k n1 is a subgraph of P k n . But n1 = k+2(i− 1)+ 1, so by using Lemma 2 we get χs(P k n1 ) ≥ k+ (i− 1)+ 1 = k+ i. As a consequence of Lemmas 1- 2 we have χs(P k n ) ≤ min{⌊n+k+1 2 ⌋, 2k + 1} for n ≥ k + 1, and χs(P k n ) ≥ ⌊n+k+1 2 ⌋ for n ∈ {k + 2i, k + 2i + 1}, where 0 ≤ i ≤ k. Moreover, 2k + 1 ≤ χs(P k n ) ≤ χs(P k n′) for all n′ ≥ n. So, we can conclude the following theorem. Theorem 2. For n ≥ k + 1, χs(P k n ) = min{⌊n+k+1 2 ⌋, 2k + 1}. Example 3. χs(P 2 10) = min{⌊10+2+1 2 ⌋, 2(2) + 1} = min{6, 5} = 5 Example 4. χs(P 3 8 ) = min{⌊8+3+1 2 ⌋, 2(3) + 1} = min{6, 7} = 6 A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1828 1 v1 2 v2 3 v3 4 v4 5 v5 1 v6 2 v7 3 v8 4 v9 5 v10 Figure 3: Star Coloring of P 2 10 1 v1 2 v2 3 v3 4 v4 5 v5 6 v6 1 v7 2 v8 Figure 4: Star Coloring of P 3 8 4. Acyclic Coloring of Ck n The technique that we followed in this section was to squeeze χa(C k n) between upper and lower bounds until we reached the exact value of χa(C k n) for a wide range of cases, and to find an upper bound and a sharp lower bound for χa(C k n) for other cases. Then we built on previous studies on the proper coloring of Ck n, and added some colors to break one of these conditions, by which we were able to determine upper bounds for χa(C k n). Let Ck n denote the cycle of order n with vertex set V (Ck n) = {v0, v1, ..., vn−1} and edge set E(Ck n)={vivj : 1 ≤ |i− j|, n− |i− j| ≤ k}. Clearly, Ck n is a complete graph when n ≤ 2k + 1 and hence χa(C k n) = n. We will start by determining a lower bound for χa(C k n) when n > 2k + 1. Theorem 3. For n > 2k + 1, χa(C k n) ≥ k + 2. Proof. Let c : V (Ck n) → {c0, c1, ..., ck} be a (k + 1)− coloring of Ck n. Since {v0, v1, ..., vk} induces a (k+1)− clique in Ck n, without loss of generality, define c by c(vj) = cj mod (k+1) for j = 0, 1, ..., n− 1. Let n = q(k+1)+ r where q ≥ 2 and 0 ≤ r ≤ k. Then we have two cases: Case 1. r > 0. Then c(vr−1) = c(vn−1) and dCn(vn−1, vr−1) = r ≤ k, a contradiction. Case 2. r = 0. For 1 ≤ i ≤ k , the induced subgraph Ci of C k n where V (Ci) = {v0, vi, v(k+1), v(k+1)+i, ..., v(q−1)(k+1), v(q−1)(k+1)+i}, is a bicolored cycle of Ck n using two colors c0 and ci, a contradiction. Hence χa(C k n) ≥ k + 2. Lemma 4. Let c ={c1, c2, ..., cr} be a proper coloring of Ck n and P = {Ti : i = 1, 2, ..., r} be the color classes of c. If CL is a bicolored cycle in Ck n, then the following holds. If Ti ∩ V (CL) ̸= ϕ then Ti ⊆ V (CL). Proof. Clearly, L is even, L ≥ 4. Obviously, when |Ti| = 2 Ti ⊆ V (CL). Now let |Ti| ≥ 3 and CL be a bicolored cycle with V (CL) = {vx1 , vy1 , vx2 , vy2 , ..., vxL 2 , vyL 2 } and A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1829 E(CL) = {vxivyi : i = 1, 2, ..., L2 } ∪ {vyivxi+1 : i = 1, 2, ..., L2 − 1} ∪ {vyL 2 vx1}. Assume that there exists vh ∈ Ti − V (CL). If vh lies between vxi and vxi+1 for some i = 1, 2, ..., L2 − 1, then dCn(vxi , vh ) < dCn(vxi , vyi) ≤ k or dCn(vh, vxi+1) < dCn(vyi , vxi+1) ≤ k, a contradiction. And if vh lies between vxL 2 and vx1 , then dCn(vxL 2 , v h ) < dCn(vxL 2 , vyi) ≤ k or dCn(vh, vx1) < dCn(vyi , vx1) ≤ k, a contradiction. Thus Ti ⊆ V (CL). Since CL is an induced bicolored cycle of Ck n, we have k < dCn(vxi , vxi+1), dCn(vyi , vyi+1) ≤ 2k for i = 1, 2, ..., L2 − 1, and k < dCn(vxL 2 , vx1), dCn(vyL 2 , vy1) ≤ 2k. Using 4 to get Ti, Tj ⊆ V (CL) are induced cycles of C2k n , and |Ti| = |Tj | ≥ n 2k for some i and j. Definition 3. A clique of Ck n is called consecutive if it is composed of vertices of consec- utive integer indices (module n). Lemma 5. [7] Let n ≥ max{3, k+ 1}, write n = q(k+ 1) + r where q ≥ 1 and 0 ≤ r ≤ k. Then χ(Ck n) = k + 1 + ⌈ rq ⌉. Lemma 6. [6] For any two integers n,k if α|n and k < h then Ck n is α−colorable if and only if Ck n contains no α+ 1 consecutive clique.. Lemma 7. [5] Let n = q(k + 1) + r where q ≥ 1 and 0 ≤ r ≤ k. Then (1) r = 0 implies that c′1 defined by c′1(vi) = i mod (k+1) is a (k+1)−proper coloring of Ck n. (2) r ̸= 0, k1 = ⌈ rq ⌉, and t = ⌊ r k1 ⌋, w = k + 1+ r − k1t, and α = k + 1+ k1 imply that c′2 defined by c′2(vi) = { ci mod α if i ∈ {0, 1, 2, ..., tα+ w − 1} c(i−(tα+w)) mod (k+1) if i ∈ {tα+ w, ..., n− 1} is a proper-coloring of Ck n using H colors only. Proof. (1) r = 0 implies that α = k + 1 divides n and by Lemma 6, Ck n can be colored using k + 1 colors. (2) Let r ̸= 0, k1 = ⌈ rq ⌉, t = ⌊ r k1 ⌋, and α = k + 1 + k1. Then we have two cases, Case 1. q = t. In this case we have q = t ≤ r k1 ≤ r r q = q, and thus k1 = r q , which implies that α = k + 1 + r q and so, qα = q(k + 1) + r = n. Therefore, α divides n and by Lemma 6, c′2 is a α− proper coloring of Ck n. Case 2. q ̸= t. Let w = k + 1 + r − k1t, and color Ck n using c′2. Notice that r ≥ k1⌊ r k1 ⌋ = k1t and r − k1 = k1( r k1 − 1) ≤ k1⌊ r k1 ⌋ = k1t which leads to 0 ≤ r − k1t ≤ k1. Thus k + 1 ≤ w ≤ α. Moreover, the cardinality of the subset of vertices {vtα+w, ..., vn−1} is a multiple of (k + 1) since n− tα− w = (q − t− 1)(k + 1) and t ≤ q − 1. Finally, note that c′2(vtα+w−1) = w − 1, and so k ≤ c′2(vtα+w−1) ≤ α − 1. Also c′2(vn−1) = k. Hence c′2 is a proper coloring of Ck n that uses at most α colors. In general when n < (k+1)2, χa(C k n) does not have a lower bound in terms of k since the value of χ(Ck n) changes as the ratio r q change, to illustrate this consider the following example. A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1830 Example 5. Let k = 5. Then: If n = 2(k + 1) + 1, then χ(Ck n) = 5 + 1 + ⌈ 1 2 ⌉ = k + 2, and χa(C k n) ≥ k + 2. If n = 2(k + 1) + 5, then χ(Ck n) = 5 + 1 + ⌈ 5 2 ⌉ = k + 4, and χa(C k n) ≥ k + 4. Remark 1. : Let n = q(k+1)+ r where q ≥ k+1 and 0 ≤ r ≤ k. Apply Lemma 7 to get k1 = 1, t = r, w = k + 1, t ̸= q, α = k + 2, and c′2(vi) = { ci mod (k+2) if i ∈ {0, 1, ..., r(k + 2) + k} c{i−r(k+2)+k+1} mod (k+1) if i ∈ {r(k + 2) + k + 1, ..., n− 1} is a (k + 2)−proper coloring of Ck n. In the following lemmas, we will consider n ≥ (k + 1)2. Lemma 8. Let n = q(k + 1) where q ≥ k + 1, and c′3(vi) = { ck+1 if i = h(k + 2) and h = 0, 1, ..., k − 1 c′1(vi) otherwise. Then: (1) c′3 is a (k + 2)− proper coloring of Ck n. (2) Ti does not induce a cycle in C2k n for 0 ≤ i ≤ k − 1. (3) c′3 is a (k + 2)− acyclic coloring of Ck n. Proof. (1) Since c′1 is a proper coloring it is enough to check the vertices with color ck+1. Since dCn(vh(k+2), v(h+1)(k+2)) = k+2 for 0 ≤ h ≤ k−1, and dCn(v(k−1)(k+2), v0) ≥ k+2, we have c′3 is a proper coloring of Ck n. (2) If q ≤ 3, then |T0| = q − 1 < q(k+1) 2k . Now, consider q > 3, then T0 does not induce a cycle in C2k n since dCn(v(q−1)(k+1), v(k+1)) ≥ 2(k + 1). Also Ti where 1 ≤ i ≤ k − 1 doesn’t induce a cycle in C2k n since vi(k+1)+i /∈ Ti and dCn(v(i−1)(k+1)+i, v(i+1)(k+1)+i) = 2(k + 1). Note that the coloring c′1 colors the vertices of Ck n by repeating c1, c2, ..., ck, which makes the distance between any two vertices having the same color be (k + 1). Adding ck+1 in c′3 denies one occurrence of each color of c1, c2, ..., ck−1 which makes a distance be- tween two vertices having the same color become 2(k + 1). Accordingly, the color classes T1, T2, ..., Tk−1 will not induce a cycle in C2k n as shown in the below table: Rule i mod(k + 1) i 0 1 ... k + 1 k + 2 k + 3 ... 2k + 3 2( k + 2) 2k + 5 ... 3k + 5 3( k + 2) 3k + 7 ... (k − 1 )( k + 2 ) − 1 (k − 1 )( k + 2 ) (k − 1 )( k + 2 ) + 1 ... q( k + 1) − 2 n − 1 c1(vi) c0 c1 ... c0 c1 c2 ... c1 c2 c3 ... c2 c3 c4 ... ck−2 ck−1 ck ... ck−1 ck c3(vi) ck+1 c1 ... c0 ck+1 c2 ... c1 ck+1 c3 ... c2 ck+1 c4 ... ck−2 ck+1 ck ... ck−1 ck ⌞ 2(k + 1) ⌟ ⌞ 2(k + 1) ⌟ A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1831 (3) Suppose that CL is a bicolored cycle in Ck n, then V (CL) = Ti ∪ Tj for some i and j. Note that k = |Tk+1| ≠ |Tk| ≥ k + 1. So V (CL) ̸= Tk+1 ∪ Tk and hence i or j ≤ k − 1. From part (2) and Lemma 4, we get a contradiction. Therefore, c′3 is a (k + 2)− acyclic coloring of Ck n. Lemma 9. Let n = (k + 1)2 + k, and c′4(vi) =  ck+2 if i = j(k + 3) for j ∈ {0, 1, ..., k − 1} ck+1 if i = k(k + 3) c′2(vi) otherwise. Then (1) c′4 is a (k + 3)−proper coloring of Ck n. (2) For 0 ≤ i ≤ k, Ti is not an induced cycle of C2k n . (3) c′4 is a (k + 3)− acyclic coloring of Ck n. Proof. (1) Since c′2 is a proper coloring, dCn(vh(k+3), v(h+1)(k+3)) = k + 3 for 0 ≤ h ≤ k − 1, and dCn(v(k−1)(k+3), v0) = k + 4, we have c′4 is a (k + 3)−proper coloring of Ck n. Moreover, to keep c′4 proper coloring, ck+1 was assigned to vn−1 instead ck+2 since dCn(v0, vn−1) = 1. (2) If k ≤ 2, then |T0| = k < (k+1)2+k 2k . If k > 2, then dCn(vk(k+2), v(k+2)) ≥ 2(k + 1). If 0 < i ≤ k, then vi(k+2)+i /∈ Ti and thus dCn(v(i−1)(k+2)+i, v(i+1)(k+2)+i) = 2(k + 2). Adding ck+2 in c′4 denies one occurrence of each color of c1, c2, ..., ck which makes a distance between two vertices having the same color become 2(k+1). Accordingly, the color classes T1, T2, ..., Tk will not induce a cycle in C2k n as shown in the below table: Rule i mod(k + 2) i 0 1 ... k + 2 k + 3 k + 4 ... 2k + 5 2( k + 2) + 2 2k + 7 ... 3k + 8 3( k + 2) + 3 ... (k − 1 )( k + 2 ) + k − 2 (k − 1 )( k + 2 ) + k − 1 (k − 1 )( k + 2 ) + k k (k + 2 ) − 1 ... k (k + 2) + k − 1 n − 1 c2(vi) c0 c1 ... c0 c1 c2 ... c1 c2 c3 ... c2 c3 ... ck−2 ck−1 ck ck+1 ... ck−1 ck c4(vi) ck+2 c1 ... c0 ck+2 c2 ... c1 ck+2 c3 ... c2 ck+2 ... ck−2 ck+2 ck ck+1 ... ck−1 ck+1 ⌞ 2(k + 2) ⌟ ⌞ 2(k + 2) ⌟ ⌞ k + 1 ⌟ (3) Assume that CL is a bicolored cycle in Ck n, then V (CL) = Ti∪Tj for some i, j. Clearly k+1 = |Tk+1| ≠ |Tk+2| = k, so i or j ≤ k say i, then Ti is not an induced cycle of C2k n . Lemma 10. Let n = q(k + 1) + r, 0 < r < k + 1, q ≥ k + 1 and n ̸= (k + 1)2 + k. Let c′5(vi) =  ck+2 if i = j(k + 3) for j ∈ {0, 1, ..., r} ck+1 if i = r(k + 3) + j(k + 2) for j ∈ {1, 2, ..., k − r} c′2(vi) otherwise. Then: A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1832 (1) c′5 is a (k + 3)−proper coloring of Ck n. (2) For i ∈ {0, ..., k}, Ti is not an induced cycle of C2k n . (3) c′5 is a (k + 3)− acyclic coloring of Ck n. Define P1 = {0, k+3, 2(k+3), ..., r(k+3)} and P2 = {r(k+3)+ (k+2), r(k+3)+ 2(k+ 2), ..., r(k + 3) + (k − r)(k + 2)}. Proof. (1) Since dCn(vh(k+3), v(h+1)(k+3)) = k+3 for 0 ≤ h ≤ r− 1, dCn(vr(k+3), v0) ≥ k + 3, dCn(vr(k+3)+h(k+2), vr(k+3)+(h+1)(k+2)) = k + 2 for 1 ≤ h ≤ k − r − 1, dCn(vn−((k−r)(k+2)−q), vk+1) ≥ k + 2 and c′2 is a proper coloring, we have c′5 is a proper coloring of Ck n. (2) To show that Ti is not an induced cycle of C2k n for i ∈ {0, ..., k}, consider the following cases Case 1. i = 0. Then v0 /∈ T0 and dCn(vn−k, vk+2) = 2k + 2. Case 2. 0 < i < r. Then vi(k+2)+i /∈ Ti and dCn(v(i−1)(k+2)+i, v(i+1)(k+2)+i) = 2(k + 2). Case 3. i = r. Then vr(k+2)+i /∈ Ti and dCn(v(r−1)(k+2)+i, vr(k+2)+(k+1)+i) = 2k + 3. Case 4. r < i < k. Then vr(k+3)+(i−r)(k+2) /∈ Ti and dCn(vr(k+3)+(i−r−1)(k+2), vr(k+3)+(i−r+1)(k+2)) = 2(k + 2). Case 5. i = k. Then vr(k+3)+(k−r)(k+2) /∈ Tk and dCn(vr(k+3)+(k−r−1)(k+2), vk) ≥ 2k + 3 when q ≤ k + 2. while dCn(vr(k+3)+(k−r−1)(k+2), vr(k+3)+(k−r+1)(k+2)) = 2(k + 2) when q ≥ k + 3. Therefore, Tk is not an induced cycle of C2k n . Adding ck+2 to P1 denies a turn of each color of c1, c2, ..., cr , and adding ck+1 to P2 does the same for colors cr+1, cr+2, ..., ck. Also the distance between the last vertex in P1 that is colored with ck+1 and the first vertex in P2 that is colored with ck+1 is (k + 1) which keeps the coloring proper as shown in the below table: Rule i mod(k + 2) (i− x)mod(k + 1) i 0 1 ... k + 2 k + 3 k + 4 ... 2 k + 5 2 (k + 3 ) 2 k + 7 ... 3 k + 8 3 (k + 3 ) ... (r − 1 )( k + 2 ) + r ... r( k + 3 ) r( k + 3 ) + 1 ... x − 1 x ... x + r x + r + 1 ... r (k + 3 ) + k + 1 r (k + 3 ) + k + 2 ... n -1 c2(vi) c0 c1 ... c0 c1 c2 ... c1 c2 c3 ... c2 c3 ... cr ... cr cr+1 ... ck c0 ... cr cr+1 ... cr cr+1 ... ck+1 c5(vi) ck+2 c1 ... c0 ck+2 c2 ... c1 ck+2 c3 ... c2 ck+2 ... cr ... ck+2 cr+1 ... ck c0 ... cr cr+1 ... cr ck+1 ... ck+1 ⌞ 2(k + 2) ⌟ ⌞ 2(k + 1) + 1 ⌟ ⌞ 2(k + 2) ⌟ ⌞ k + 1 ⌟ x = r(k + 2) + k + 1 (3) Since dCn(v0, vk+1) = k + 1 and Ti not an induced cycle of C2k n for i ≤ k, c′5 is a (k + 3)− acyclic coloring for Ck n. Lemma 11. Let n = q(k + 1) + r, 0 < r ≤ k, q ≥ k + 1, q − r ≥ k + 1 and c′6(vi) = { ck+1 if i = (r + j)(k + 2) + (k + 1) for j ∈ {0, 1, ..., k − 1} c′2(vi) otherwise. A. Etawi, M. Ghanem, H. Al-Ezeh / Eur. J. Pure Appl. Math, 15 (4) (2022), 1822-1835 1833 Then: (1) c′6 is a (k + 2)−proper coloring of Ck n. (2) For i ∈ {0, ..., k − 1}, Ti is not an induced cycle of C2k n . (3) c′6 is a (k + 2)− acyclic coloring of Ck n. Proof. (1) Note that dCn(v(r+h)(k+2)+k+1, v(r+h+1)(k+2)+k+1) = k+2 for 0 ≤ h ≤ k−2, dCn(v(r+k−1)(k+2)+k+1, vk+1) ≥ k+3, and dCn(vr(k+2)−1, vr(k+2)+k+1) = k+2. Therefore, c′6 is a proper coloring of Ck n. (2) For 0 ≤ i < k − 1, v(r+i)(k+2)+(k+1) /∈ Ti and dCn(v(r+i)(k+2), v(r+i)(k+2)+2(k+1)) = 2(k + 1). For i = k − 1 we have the following two cases: Case 1. q − r > k + 1. Then v(r+k−1)(k+2)+(k+1) /∈ Tk−1 and dCn(v(r+k−1)(k+2), v(r+k−1)(k+2)+2(k+1)) = 2(k + 1). Case 2. : q − r = k + 1. Then v(r+k−1)(k+2)+(k+1) /∈ Tk−1 and dCn(v(r+k−1)(k+2), vk−1) = 2(k + 1). Hence Ti is not an induced cycle of C2k n for i ∈ {0, ..., k − 1}. (3) Note that r + k = |Tk+1| ̸= |Tk| ≥ r + k + 1. Moreover, Ti is not an induced cycle in C2k n for i ≤ k − 1, so c′6 is a (k + 2)− acyclic coloring for Ck n. As a consequence of Lemmas 4-11 we get the following theorem. Theorem 4. Let Ck n be the kth-power of a cycle of order n. Then (1) k + 2 ≤ χa(C k n) ≤ k + 3 if n ≥ (k + 1)2. (2) χa(C k n) = k + 2 if n = q(k + 1) + r and q − r ≥ k + 1. (3) χa(C k n) = k + 2 if n ≥ (k + 1)3. According to Theorem 4 when n is between (k+1)2 and (k+1)3, χa(C k n) varies between k + 2 and k + 3, while for n ≥ (k + 1)3, χa(C k n) = k + 2. The following example shows that k + 2 is a sharp lower bound for χa(C k n) when n = (k + 1)2. Example 6. Let k = 2 and n = (k + 1)2, then c′2(C k n) uses only 4 colors to acyclic color Ck n, χa(C k n) = k + 2. The union of any two color classes induces a disjoint collection of trees. 1 v1 2 v2 3 v3 1 v4 2 v5 4 v6 1 v7 3 v8 4 v9 T1,T2 T1,T3 T1,T4 T2,T3 T2,T4 T3,T4 v1 v2 v4 v5 v7 v1 v3 v4 v7 v8 v4 v6 v7 v9 v1 v2 v3 v5 v8 v9 v2 v5 v6 v6 v8 v9 v3 REFERENCES 1834 5. Star Coloring of Ck n In this section we bound χs(C k n) between two values by combining some results from previous sections with the relation between χs(G) and χ(G2). Lemma 12. [4] Let G be a graph of order n and G2 be the square graph of G. Then, χs(G) ≤ χ(G2), where χ(G) denotes the (proper) chromatic number of G. Theorem 5. For n ≥ (k + 1)2, 2k + 1 ≤ χs(C k n) ≤ 2k + 2. Proof. Let n = q(k+1)+r. Using Lemmas 5 and 12 to get χ(C2k n ) = 2k+1+ ⌈ r q ⌉ = 2k+2 and χs(C k n) ≤ 2k + 2. Moreover, P k n is a subgraph of Ck n, so χs(P k n ) ≤ χs(C k n). According to Lemma 1 χs(P k n ) = 2k + 1, so 2k + 1 ≤ χs(C k n). The following example shows that k + 2 is a sharp lower bound for χa(C k n). Example 7. Let k = 2 and n = (k + 1)2 + 1, then c(Ck n) uses only 5 colors to star color C2 10, χs(C k n) = 2k + 1. The union of any two color classes induces a disjoint collection of stars. 1 v1 2 v2 3 v3 4 v4 5 v51 v6 4 v7 2 v8 3 v9 5 v10T1,T2 T1,T3 T1,T4 T1,T5 T2,T3 T2,T4 T2,T5 T3,T4 T3,T5 T4,T5 v1 v2 v6 v7 v9 v1 v3 v6 v4 v6 v7 v1 v10 v1 v5 v6 v2 v3 v8 v9 v2 v4 v7 v8 v8 v10 v2 v5 v3 v4 v7 v9 v3 v5 v9 v10 v4 v5 v7 v10 References [1] H. L. Bodlaender, M. R. Fellows, M. T. Hallett, H. T. Wareham, and T. J. Warnow. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science, 244:167–188, 2000. [2] M.I. Burstein. Every 4-valent graph has an acyclic 5-coloring. Soobshch. Akad. Nauk Gruzin SSR, 93:21–24, 1979. [3] B. Grunbaum. Acyclic colorings of planar graphs. Isr.J. Math, 19:390–412, 1973. [4] F. Guillaume, A. Raspaud, and B. Reed. Star coloring of graphs. Journal of Graph Theory Wiley, 47(3):163–182, 2004. [5] M. F. Jimenez and M.V. Pabon. A note on coloring powers of cycles. Research Report 18A - 70, Facultad de Ciencias de la Universidad de los Andes, Bogota, Colombia, 2005. REFERENCES 1835 [6] J. B. Orlin, M. A. Bonuccelli, and D. P. Bovet. An o(n2) algorithm for coloring proper circular arc graphs. SIAM J. Alg. Disc. Meth., 2(2):88–93, 1981. [7] A. Prowse and D. R. Woodall. Choosability of powers of circuits. Graphs and Com- binatorics, 19:137–144, 2003. [8] N. Vedavathi and D. Gurram. Applications on graph theory. International Journal of Engineering Research and Technology, 2(1):1–4, 2013. [9] J. Wang, L. Y. Miao, J. B. Li, and Y. L. Liu. Acyclic choosability of graphs with bounded degree. Acta Mathematica Sinica English Series, 38:560–570, 2022. [10] D. R. Wood. Acyclic, star and oriented colourings of graph subdivisions. Discrete Mathematics and Theoretical Computer Science, 7:37–50, 2005.