Graceful Colorings of Graphs

Abstract

A graceful labeling of a graph $G$ of order $n$ and size $m$ is a one-to-one function $f:V(G)\to \{0,1,\dots ,m\}$ that induces a one-to-one function $f^{\prime }:E(G)\to \{1,2,\dots ,m\}$ defined by $f^{\prime }(uv)=|f(u)–f(v)|$. A graph that admits a graceful labeling is a graceful graph. A proper coloring $c:V(G)\to \{1,2,\dots ,k\}$ is called a graceful $k$-coloring if the induced edge coloring $c^{\prime }$ defined by $c^{\prime }(uv)=|c(u)–c(v)|$ is proper. The minimum positive integer $k$ for which $G$ has a graceful $k$-coloring is its graceful chromatic number ${\chi }_g(G)$. The graceful chromatic numbers of cycles, wheels, and caterpillars are determined. An upper bound for the graceful chromatic number of trees is determined in terms of its maximum degree.