Graceful Colorings of Graphs

A graceful labeling of a graph \( G \) of order \( n \) and size \( m \) is a one-to-one function \( f : V(G) \rightarrow \{0, 1, \ldots, m\} \) that induces a one-to-one function \( f’ : E(G) \rightarrow \{1, 2, \ldots, m\} \) defined by \( f'(uv) = |f(u) – f(v)| \). A graph that admits a graceful labeling is a graceful graph. A proper coloring \( c : V(G) \rightarrow \{1, 2, \ldots, k\} \) is called a graceful \( k \)-coloring if the induced edge coloring \( c’ \) defined by \( c'(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.