# Article

 Title: On graceful colorings of trees (English) Author: English, Sean Author: Zhang, Ping Language: English Journal: Mathematica Bohemica ISSN: 0862-7959 (print) ISSN: 2464-7136 (online) Volume: 142 Issue: 1 Year: 2017 Pages: 57-73 Summary lang: English . Category: math . Summary: A proper coloring $c\colon V(G)\to \{1, 2,\ldots , k\}$, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c'\colon 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 \frac 5{3}\Delta \rceil$ and this bound is best possible. It is shown for each integer $\Delta \ge 2$ that there is an infinite class of trees $T$ with maximum degree $\Delta$ such that $\chi _g(T)=\lceil \frac 5{3}\Delta \rceil$. In particular, we investigate for each integer $\Delta \ge 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 \ge 2$ when $1 \le h \le 4$. Furthermore, it is shown for each $\Delta \ge 2$ that $\lim _{h \to \infty } \chi _g(T_{\Delta , h}) = \lceil \frac 5{3}\Delta \rceil$. (English) Keyword: graceful coloring Keyword: graceful chromatic numbers Keyword: tree MSC: 05C05 MSC: 05C15 MSC: 05C78 idZBL: Zbl 06738570 idMR: MR3619987 DOI: 10.21136/MB.2017.0035-15 . Date available: 2017-02-21T17:21:54Z Last updated: 2018-04-02 Stable URL: http://hdl.handle.net/10338.dmlcz/146009 . Reference: [1] Bi, Z., Byers, A., English, S., Laforge, E., Zhang, P.: Graceful colorings of graphs.(to appear) in J. Combin. Math. Combin. Comput. Reference: [2] Cayley, A.: On the theory of analytical forms called trees.Philos. Mag. (4) 85 (1857), 172-176. MR 1505295, 10.1080/14786445708642275 Reference: [3] Chartrand, G., Zhang, P.: Chromatic Graph Theory.Discrete Mathematics and Its Applications Chapman & Hall/CRC Press, Boca Raton (2009). Zbl 1169.05001, MR 2450569 Reference: [4] Gallian, J. A.: A dynamic survey of graph labeling.Electron. J. Comb. DS6, Dynamic Surveys (electronic only) (1998), 43 pages. Zbl 0953.05067, MR 1668059 Reference: [5] Golomb, S. W.: How to number a graph.Graph Theory and Computing Academic Press, New York (1972), 23-37. Zbl 0293.05150, MR 0340107, 10.1016/B978-1-4832-3187-7.50008-8 Reference: [6] Kirchhoff, G.: Ü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. 10.1002/andp.18471481202 Reference: [7] Rosa, A.: On certain valuations of the vertices of a graph.Theory of Graphs Gordon and Breach, New York (1967), 349-355. Zbl 0193.53204, MR 0223271 .

## Files

Files Size Format View
MathBohem_142-2017-1_6.pdf 340.5Kb application/pdf View/Open

Partner of