The $t$-Tone Chromatic Number of Classes of Sparse Graphs

Abstract

For a graph $G$ and $t,k\in {\mathbb{Z}}^{+}$ a \emph{$t$-tone $k$-coloring} of $G$ is a function $f:V(G)\to \left(\genfrac{}{}{0ex}{}{[k]}{t}\right)$ such that $|f(v)\cap f(w)|<d(v,w)$ for all distinct $v,w\in V(G)$. The \emph{$t$-tone chromatic number} of $G$, denoted ${\tau }_t(G)$, is the minimum $k$ such that $G$ is $t$-tone $k$-colorable. For small values of $t$, we prove sharp or nearly sharp upper bounds on the $t$-tone chromatic number of various classes of sparse graphs. In particular, we determine ${\tau }_2(G)$ exactly when $\text{mad}(G)<12/5$ and bound ${\tau }_2(G)$, up to a small additive constant, when $G$ is outerplanar. We also determine ${\tau }_t(C_n)$ exactly when $t\in \{3,4,5\}$.

15 pages, 6 figures, version 2 corrects a few typos