On graceful colorings of trees. (English) Zbl 1463.05165

English, Sean; Zhang, Ping

Math. Bohem. 142, No. 1, 57-73 (2017).

Summary: A proper coloring \(c\colon V(G)\to\{1,2,\ldots ,k\}\), \(k\geq 2\) of a graph \(G\) is called a graceful \(k\)-coloring if the induced edge coloring \(c'\colon E(G)\to\{1,2,\dots ,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)\leq\lceil\frac53\Delta\rceil\) and this bound is best possible. It is shown for each integer \(\Delta\geq 2\) 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\geq 2\) 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\geq 2\) when \(1\leq h\leq 4\). Furthermore, it is shown for each \(\Delta\geq 2\) that \(\lim_{h\to\infty}\chi_g(T_{\Delta ,h})=\lceil\frac53\Delta\rceil\).

MSC:

05C15	Coloring of graphs and hypergraphs
05C78	Graph labelling (graceful graphs, bandwidth, etc.)

Keywords:

graceful coloring; graceful chromatic numbers; tree