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.






Nonlinear Analysis

How to Cite

Acyclic and Star Coloring of Powers of Paths and Cycles. (2022). European Journal of Pure and Applied Mathematics, 15(4), 1822-1835.

Similar Articles

1-10 of 27

You may also start an advanced similarity search for this article.