Acyclic and Star Coloring of Powers of Paths and Cycles


  • Ali Etawi The University of Jordan
  • Manal Ghanem
  • Hasan Al-Ezeh



Acyclic Coloring, Powers of Cycles, Powers of Paths, Star Coloring


Let $G=(V,E)$ be a graph. The $k^{th}-$ power of $G$ denoted by $G^{k}$ 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 denoted by $\chi_{a}(G)(\chi_{s}(G))$. In this paper we prove that for $n\geq k+1,$ $\chi_{s}(P_{n}^{k})=\min\{\lfloor\frac{k+n+1}{2}\rfloor,2k+1\}$ and $\chi_{a}(P_{n}^{k})=k+1.$ Further we show that for $n\geq(k+1)^{2}$, $%2k+1\leq\chi _{s}(C_{n}^{k})\leq2k+2$ and $k+2\leq\chi_{a}(C_{n}^{k})\leq k+3.$ Finally, we derive the formula $\chi_{a}(C_{n}^{k})=k+2$ for $% n\geq(k+1)^{3}.$

Author Biography

Hasan Al-Ezeh

This auther has passed away, he was one of the supervisors. He was a professor in The University of Jordan.

Since the email is mandatory field, and his email is no longer valid so another email of the first auther was added.




How to Cite

Etawi, A., Ghanem, M., & Al-Ezeh, H. (2022). Acyclic and Star Coloring of Powers of Paths and Cycles. European Journal of Pure and Applied Mathematics, 15(4), 1822–1835.



Nonlinear Analysis