Acyclic and Star Coloring of Powers of Paths and Cycles

Abstract

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\ge 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\ge (k+1{)}^2$, $$ and $k+2\le {\chi }_a(C_n^k)\le k+3.$ Finally, we derive the formula ${\chi }_a(C_n^k)=k+2$ for $$