New results in \(t\)-tone coloring of graphs (Q1953497)

Summary: A \(t\)-tone \(k\)-coloring of \(G\) assigns to each vertex of \(G\) a set of \(t\) colors from \(\{1,\dots,k\}\) so that vertices at distance \(d\) share fewer than \(d\) common colors. The \(t\)-tone chromatic number of \(G\), denoted \(t(G)\), is the minimum \(k\) such that \(G\) has a \(t\)-tone \(k\)-coloring. \textit{A. Bickle} and \textit{B. Phillips} [``\(t\)-tone colorings of graphs'' (submitted)] showed that always \(\tau_2(G) \leq [\Delta(G)]^2 +\Delta(G)\), but conjectured that in fact \(\tau_2(G) \leq 2\Delta(G) + 2\); we confirm this conjecture when \(\Delta(G) \leq 3\) and also show that always \(\tau_2(G) \leq \left\lceil (2 +\sqrt{2}) \Delta(G) \right\rceil\). For general \(t\) we prove that \(\tau_t(G) \leq (t^2+t) \Delta(G)\). Finally, for each \(t \geq 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)} \leq \tau_t(T) \leq c_2\sqrt{\Delta(T)}\).