«MAR SEP Oct 2 2016 2017 2018 2 captures 4 Mar 17 - 2 Sep 17

Close Help

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 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