A structural approach to the graceful coloring of a subclass of trees

Abstract

Let $M=\{1,2,..m\}$ and G be a simple graph. A graceful m-coloring of G is a proper vertex coloring of G using the colors in M which leads to a proper edge coloring using $M\setminus \left\{m\right\}$ colors such that the associated color of each edge is the absolute difference between their end vertices. The graceful chromatic number ${\chi }_g\left(G\right)=\text{min}\{m:G\text{admits a graceful}\text{m}\text{- coloring}\}$. We prove that $5\le {\chi }_g\left(T\right)\le 7$, where T is a tree with $\Delta =4$. Furthermore, we categorize the trees into three types along with its characterization and the related coloring algorithm are presented in this study.

Keywords: Coloring algorithm; Graceful chromatic number; Graceful coloring; Trees.