New results in $t$-tone coloring of graphs

A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,\mathrm{.}\mathrm{.}\mathrm{.},k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The {\it $t$-tone chromatic number} of $G$, denoted ${\tau }_t(G)$, is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. Bickle and Phillips showed that always $\tau_2(G) \le [\Delta(G)]^2 + \Delta(G)$,butconjecturedthatinfact$\tau_2(G) \le 2\Delta(G) + 2$; we confirm this conjecture when $\mathrm{\Delta }(G)\le 3$ and also show that always ${\tau }_2(G)\le \text{ceil}(2+\sqrt{2})\mathrm{\Delta }(G)$. For general $t$ we prove that ${\tau }_t(G)\le (t^2+t)\mathrm{\Delta }(G)$. Finally, for each $t\ge 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{\Delta(T)} \le \tau_t(T) \le c_2\sqrt{\Delta(T)}$.