| 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:
|
2020-07-01 |
| 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 |
| . |
