Institute of Mathematics

Abstract:  A proper coloring $c V(G)\to\{1, 2,\ldots, k\}$, $k\ge2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c' E(G) \to\{1, 2, \ldots, k-1\}$ defined by $c'(uv)=|c(u)-c(v)|$ for each edge $uv$ of $G$ is also proper. The minimum integer $k$ for which $G$ has a graceful $k$-coloring is the graceful chromatic number $\chi_g(G)$. It is known that if $T$ is a tree with maximum degree $\Delta$, then $\chi_g(T) \le\lceil\frac53\Delta\rceil$ and this bound is best possible. It is shown for each integer $\Delta\ge2$ that there is an infinite class of trees $T$ with maximum degree $\Delta$ such that $\chi_g(T)=\lceil\frac53\Delta\rceil$. In particular, we investigate for each integer $\Delta\ge2$ a class of rooted trees $T_{\Delta, h}$ with maximum degree $\Delta$ and height $h$. The graceful chromatic number of $T_{\Delta, h}$ is determined for each integer $\Delta\ge2$ when $1 \le h \le4$. Furthermore, it is shown for each $\Delta\ge2$ that $\lim_{h \to\infty} \chi_g(T_{\Delta, h}) = \lceil\frac53\Delta\rceil$.