# On graceful colorings of trees

Mathematica Bohemica (2017)

- Volume: 142, Issue: 1, page 57-73
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topEnglish, Sean, and Zhang, Ping. "On graceful colorings of trees." Mathematica Bohemica 142.1 (2017): 57-73. <http://eudml.org/doc/287893>.

@article{English2017,

abstract = {A proper coloring $c\colon V(G)\rightarrow \lbrace 1, 2,\ldots , k\rbrace $, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^\{\prime \}\colon E(G) \rightarrow \lbrace 1, 2, \ldots , k-1\rbrace $ defined by $c^\{\prime \}(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 \rightarrow \infty \} \chi _g(T_\{\Delta , h\}) = \lceil \frac\{5\}\{3\}\Delta \rceil $.},

author = {English, Sean, Zhang, Ping},

journal = {Mathematica Bohemica},

keywords = {graceful coloring; graceful chromatic numbers; tree},

language = {eng},

number = {1},

pages = {57-73},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {On graceful colorings of trees},

url = {http://eudml.org/doc/287893},

volume = {142},

year = {2017},

}

TY - JOUR

AU - English, Sean

AU - Zhang, Ping

TI - On graceful colorings of trees

JO - Mathematica Bohemica

PY - 2017

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 142

IS - 1

SP - 57

EP - 73

AB - A proper coloring $c\colon V(G)\rightarrow \lbrace 1, 2,\ldots , k\rbrace $, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^{\prime }\colon E(G) \rightarrow \lbrace 1, 2, \ldots , k-1\rbrace $ defined by $c^{\prime }(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 \rightarrow \infty } \chi _g(T_{\Delta , h}) = \lceil \frac{5}{3}\Delta \rceil $.

LA - eng

KW - graceful coloring; graceful chromatic numbers; tree

UR - http://eudml.org/doc/287893

ER -

## References

top- Bi, Z., Byers, A., English, S., Laforge, E., Zhang, P., Graceful colorings of graphs, (to appear) in J. Combin. Math. Combin. Comput.
- Cayley, A., 10.1080/14786445708642275, Philos. Mag. (4) 85 (1857), 172-176. (1857) MR1505295DOI10.1080/14786445708642275
- Chartrand, G., Zhang, P., Chromatic Graph Theory, Discrete Mathematics and Its Applications Chapman & Hall/CRC Press, Boca Raton (2009). (2009) Zbl1169.05001MR2450569
- Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Comb. DS6, Dynamic Surveys (electronic only) (1998), 43 pages. (1998) Zbl0953.05067MR1668059
- Golomb, S. W., 10.1016/B978-1-4832-3187-7.50008-8, Graph Theory and Computing Academic Press, New York (1972), 23-37. (1972) Zbl0293.05150MR0340107DOI10.1016/B978-1-4832-3187-7.50008-8
- Kirchhoff, G., 10.1002/andp.18471481202, Annalen der Physik 148 (1847), 497-508 German. (1847) DOI10.1002/andp.18471481202
- Rosa, A., On certain valuations of the vertices of a graph, Theory of Graphs Gordon and Breach, New York (1967), 349-355. (1967) Zbl0193.53204MR0223271

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.