MATHEMATICA BOHEMICA, Vol. 142, No. 1, pp. 57-73, 2017

On graceful colorings of trees

Sean English, Ping Zhang

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

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

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 2010): 05C15, 05C78

DOI: 10.21136/MB.2017.0035-15

Full text available as PDF.


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


Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.

[Previous Article] [Next Article] [Contents of This Number] [Contents of Mathematica Bohemica] [Full text of the older issues of Mathematica Bohemica at DML-CZ]