Previous |  Up |  Next


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:
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 Size Format View
MathBohem_142-2017-1_6.pdf 340.5Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo