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

    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.

Downloads

Published

2022-10-31

Issue

Section

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