Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graceful coloring; graceful chromatic numbers; tree
graceful coloring; graceful chromatic numbers; tree
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 $.
References:
[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 10.1080/14786445708642275 | MR 1505295
[3] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Discrete Mathematics and Its Applications Chapman & Hall/CRC Press, Boca Raton (2009). MR 2450569 | Zbl 1169.05001
[4] Gallian, J. A.: A dynamic survey of graph labeling. Electron. J. Comb. DS6, Dynamic Surveys (electronic only) (1998), 43 pages. MR 1668059 | Zbl 0953.05067
[5] Golomb, S. W.: How to number a graph. Graph Theory and Computing Academic Press, New York (1972), 23-37. DOI 10.1016/B978-1-4832-3187-7.50008-8 | MR 0340107 | Zbl 0293.05150
[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 10.1002/andp.18471481202
[7] Rosa, A.: On certain valuations of the vertices of a graph. Theory of Graphs Gordon and Breach, New York (1967), 349-355. MR 0223271 | Zbl 0193.53204
Search
Partner of
