Originators: Gary Chartrand (presented by Bill Kinnersley - REGS 2011)
Definitions: A t-tone coloring of a graph $G$ is an assignment of $t$-sets of colors to the vertices of $G$ such that if the distance between vertices $u$ and $v$ is $d$, then they receive fewer than $d$ common colors. The $t$-tone chromatic number of $G$, denoted $\tau_t(G)$, is the minimum number of colors in a $t$-tone coloring of $G$.
Background: Gary Chartrand introduced $t$-tone coloring as a generalization of proper coloring, which is equivalent to 1-tone coloring. The concept was initially studied in a research group directed by Ping Zhang, consisting of Fonger, Goss, Phillips, and Segroves [FGPS]. They showed that always $\tau_t(G) \le \sum_{i=1}^t \chi(G^i)$ and determined $\tau_2(G)$ when $G$ is a tree or a complete multipartite graph. Bickle and Phillips [BP] published additional results, including the exact value of $\tau_t(P_n)$ for general $t$ and a characterization of cubic graphs $G$ such that $\tau_2(G) = 5$.
Conjecture 1 (Bickle, Phillips 2011+): If $G$ has maximum degree $d$, then $\tau_2(G) \le 2d + 2$, with equality if and only if either $G$ contains $K_{d+1}$ or $d = 2$ and $G$ is $C_4$ or $C_7$.
Comments: Fonger, Goss, Phillips, and Segroves proved $\tau_2(G)\le\chi(G^2)+\chi(G)$. Bickle and Phillips showed $\tau_2(G)\le d^2+d$, which can be stronger when $G^2$ is complete. The bound has since been improved to $\tau_2(G) \le \lceil (2 + \sqrt{2})d \rceil$ [CKK]. Labels assigned to vertices of a complete graph must be disjoint, so $\tau_t(K_n) = tn$; hence Conjecture 1 is sharp.
This conjecture is open even in the case $(t,d)=(2,3)$. That is, it is not known whether all graphs with maximum degree 3 can be 2-tone colored using only 8 colors. (It is known that 10 colors suffice.) For this special case, Bickle and Phillips posed a stronger conjecture: that 8 colors always suffice, 7 colors suffice for all graphs not containing $K_4$, and 6 colors suffice for all graphs not containing $K_4-e$.
It may be interesting to consider general $t$. The same techniques used to show $\tau_2(G) \le \lceil (2 + \sqrt{2})d \rceil$ can be extended to show $\tau_t(G) \le (t^2+t)d$. This upper bound is linear in $d$ and quadratic in $t$; perhaps the asymptotics can be improved. Since $\tau_t(K_n) = tn$, we cannot hope to find a bound that is sublinear in $d$. Moreover, Bickle and Phillips showed that $\tau_t(P_n) = \Theta(t^{3/2})$, so in any upper bound on $\tau_t(G)$ the exponent on $t$ must be at least 3/2.
Problem 2: Determine bounds on $\tau_t(T)$ in terms of $\Delta(T)$ when $T$ is a tree.
Comments: Fonger, Goss, Phillips, and Segroves proved that $\tau_2(T) = \left (5 + \sqrt{1 + 8\Delta(T)} \right )/2$ when $T$ is a tree. Their argument does not extend to larger $t$, and in the general case it seems unlikely that $\tau_t(T)$ is completely determined by $\Delta(T)$. Even when $T$ is a star, determining the exact value of $\tau_t(T)$ seems nontrivial.
Determination of $\tau_t(K_{1,k})$ would yield, as a corollary, the exact value of $\tau_t(G)$ whenever $G$ is a complete multipartite graph. In this situation, no color may appear on more than one partite set, so it suffices to determine how many colors must be used on each partite set. Vertices in each partite set lie at pairwise distance 2, so coloring them is analogous to coloring the leaves of a star.
Whenever $s \le t$, we have $\tau_s(G) \le \tau_t(G)$, since discarding all but $s$ colors from each label of a $t$-tone coloring of $G$ leaves an $s$-tone coloring. Thus the result of Fonger, Goss, Phillips, and Segroves on 2-tone colorings of trees implies that if $T$ is a tree and $t \ge 2$, then $\tau_t(G) \ge c_1 [\Delta(T)]^{1/2}$ for some constant $c_1$. For $t=3$ and $t=4$, REGS participants [CKK] showed the existence of a constant $c_2$ such that $\tau_t(T) \le c_2 [\Delta(T)]^{1/2}$. This was already known for $t=2$ and remains open for $t \ge 5$.
Problem 3: Determine bounds on $\tau_t(G)$ in terms of $\Delta(G)$ when $G$ is planar.
Comments: Here we again know that $\tau_t(G) \ge c_1 [\Delta(G)]^{1/2}$ for some constant $c_1$. REGS participants [CKK] nontrivial upper bounds: there is a constant $c_2$ such that $\tau_t(G) \le c_2 [\Delta(G)]^{(t-1)/t}$. The exponents on $\Delta(G)$ in these two bounds coincide when $t=2$, but they differ when $t \ge 3$. Both bounds apply not just to planar graphs, but to all graphs with bounded degeneracy.
Problem 4: Determine bounds on $\tau_t(G \Box H)$ in terms of $\tau_t(G)$ and $\tau_t(H)$.
Comments: For standard vertex-coloring, it is known that $\chi(G \Box H) = \max \{\chi(G), \chi(H)\}$. It is not hard to show that $\tau_t(G \Box H) \le \tau_t(G) \cdot \tau_t(H)$, but this does not seem to be a very good bound.
References:
[BP] A. Bickle, B. Phillips, $t$-Tone Colorings of Graphs, preprint.
[CKK] D. Cranston, J. Kim, and W. Kinnersley, New results in $t$-tone
coloring of graphs, submitted.
http://arxiv.org/abs/1108.4751
[FGPS] N. Fonger, J. Goss, B. Phillips, and C. Segroves, Math 6450: Final
Report,
http://homepages.wmich.edu/~zhang/finalReport2.pdf