Acyclic and Star Coloring of Powers of Paths and Cycles

Authors

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

DOI:

https://doi.org/10.29020/nybg.ejpam.v15i4.4574

Keywords:

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

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\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

Downloads

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. https://doi.org/10.29020/nybg.ejpam.v15i4.4574