On graceful colorings of trees

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