New results in $t$-tone coloring of graphs

Abstract

A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,...,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)$, but conjectured that in fact ${\tau }_2(G)\le 2\Delta (G)+2$; we confirm this conjecture when $\Delta (G)\le 3$ and also show that always $τ_2(G) \le \ceil{(2 + \sqrt{2})Δ(G)}$. For general $t$ we prove that ${\tau }_t(G)\le (t^2+t)\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)}$.

arXiv comment13 pages, 1 figure