Geodesic
On graceful colorings of trees
Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 57-73
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 $.
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 $.
DOI : 10.21136/MB.2017.0035-15
Classification : 05C05, 05C15, 05C78
Keywords: graceful coloring; graceful chromatic numbers; tree 
@article{10_21136_MB_2017_0035_15,
     author = {English, Sean and Zhang, Ping},
     title = {On graceful colorings of trees},
     journal = {Mathematica Bohemica},
     pages = {57--73},
     year = {2017},
     volume = {142},
     number = {1},
     doi = {10.21136/MB.2017.0035-15},
     mrnumber = {3619987},
     zbl = {06738570},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0035-15/}
}
TY  - JOUR
AU  - English, Sean
AU  - Zhang, Ping
TI  - On graceful colorings of trees
JO  - Mathematica Bohemica
PY  - 2017
SP  - 57
EP  - 73
VL  - 142
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0035-15/
DO  - 10.21136/MB.2017.0035-15
LA  - en
ID  - 10_21136_MB_2017_0035_15
ER  - 
%0 Journal Article
%A English, Sean
%A Zhang, Ping
%T On graceful colorings of trees
%J Mathematica Bohemica
%D 2017
%P 57-73
%V 142
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0035-15/
%R 10.21136/MB.2017.0035-15
%G en
%F 10_21136_MB_2017_0035_15
English, Sean; Zhang, Ping. On graceful colorings of trees. Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 57-73. doi: 10.21136/MB.2017.0035-15

[1] Bi, Z., Byers, A., English, S., Laforge, E., Zhang, P.: Graceful colorings of graphs. (to appear) in J. Combin. Math. Combin. Comput.

[2] Cayley, A.: On the theory of analytical forms called trees. Philos. Mag. (4) 85 (1857), 172-176. | DOI | MR

[3] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Discrete Mathematics and Its Applications Chapman & Hall/CRC Press, Boca Raton (2009). | MR | JFM

[4] Gallian, J. A.: A dynamic survey of graph labeling. Electron. J. Comb. DS6, Dynamic Surveys (electronic only) (1998), 43 pages. | MR | JFM

[5] Golomb, S. W.: How to number a graph. Graph Theory and Computing Academic Press, New York (1972), 23-37. | DOI | MR | JFM

[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. | DOI

[7] Rosa, A.: On certain valuations of the vertices of a graph. Theory of Graphs Gordon and Breach, New York (1967), 349-355. | MR | JFM

Cité par Sources :