# Institute of Mathematics

## On graceful colorings of trees

#### Sean English, Ping Zhang

###### Received July 9, 2015.  First published November 7, 2016.

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$.
Keywords:  graceful coloring; graceful chromatic numbers; tree
Classification MSC:  05C15, 05C78
DOI:  10.21136/MB.2017.0035-15

References:
[1] Z. Bi, A. Byers, S. English, E. Laforge, P. Zhang: Graceful colorings of graphs. (to appear) in J. Combin. Math. Combin. Comput.
[2] A. Cayley: On the theory of analytical forms called trees. Philos. Mag. (4) 85 (1857), 172-176. DOI 10.1080/14786445708642275
[3] G. Chartrand, P. Zhang: Chromatic Graph Theory. Discrete Mathematics and Its Applications Chapman & Hall/CRC Press, Boca Raton (2009). MR 2450569 | Zbl 1169.05001
[4] J. A. Gallian: A dynamic survey of graph labeling. Electron. J. Comb. DS6, Dynamic Surveys (electronic only) (1998), 43 pages. MR 1668059 | Zbl 0953.05067
[5] S. W. Golomb: How to number a graph. Graph Theory and Computing Academic Press, New York (1972), 23-37. DOI 10.1016/B978-1-4832-3187-7.50008-8 | MR 0340107 | Zbl 0293.05150
[6] G. Kirchhoff: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme gefürht wird. Annalen der Physik 148 (1847), 497-508 German. DOI 10.1002/andp.18471481202
[7] A. Rosa: On certain valuations of the vertices of a graph. Theory of Graphs Gordon and Breach, New York (1967), 349-355. MR 0223271 | Zbl 0193.53204

Affiliations:   Sean English, Ping Zhang, Department of Mathematics, Western Michigan University, 1903 W Michigan Ave, Kalamazoo, MI 49008-5248, USA, e-mail: sean.j.english@wmich.edu, ping.zhang@wmich.edu

PDF available at: