On graceful colorings of trees

English, Sean ; Zhang, Ping

Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 57-73.

Résumé

A proper coloring $c:V(G)\to \{1,2,\dots ,k\}$, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^{\prime }:E(G)\to \{1,2,\dots ,k-1\}$ defined by $c^{\prime }(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 $\mathrm{\Delta }$, then ${\chi }_g(T)\le \lceil \frac{5}{3}\mathrm{\Delta }\rceil$ and this bound is best possible. It is shown for each integer $\mathrm{\Delta }\ge 2$ that there is an infinite class of trees $T$ with maximum degree $\mathrm{\Delta }$ such that ${\chi }_g(T)=\lceil \frac{5}{3}\mathrm{\Delta }\rceil$. In particular, we investigate for each integer $\mathrm{\Delta }\ge 2$ a class of rooted trees $T_{\mathrm{\Delta },h}$ with maximum degree $\mathrm{\Delta }$ and height $h$. The graceful chromatic number of $T_{\mathrm{\Delta },h}$ is determined for each integer $\mathrm{\Delta }\ge 2$ when $1\le h\le 4$. Furthermore, it is shown for each $\mathrm{\Delta }\ge 2$ that $\underset{h\to \mathrm{\infty }}{lim}{\chi }_g(T_{\mathrm{\Delta },h})=\lceil \frac{5}{3}\mathrm{\Delta }\rceil$.

Détail

DOI : 10.21136/MB.2017.0035-15

Classification : 05C05, 05C15, 05C78
Mots-clés : graceful coloring; graceful chromatic numbers; tree