The t-tone chromatic number of random graphs

Abstract

A proper 2-tone $k$-coloring of a graph is a labeling of the vertices with elements from $\left(\genfrac{}{}{0ex}{}{[k]}{2}\right)$ such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph $G$, denoted ${\tau }_2(G)$ is the smallest $k$ such that $G$ admits a proper 2-tone $k$ coloring. In this paper, we prove that w.h.p. for $p\ge C{n}^{-1/4}{\ln }^{9/4}n$, ${\tau }_2(G_{n,p})=(2+o(1))\chi (G_{n,p})$ where $\chi$ represents the ordinary chromatic number. For sparse random graphs with $p=c/n$, $c$ constant, we prove that ${\tau }_2(G_{n,p})=\lceil \sqrt{8\Delta +1}+5/2\rceil$ where $\Delta$ represents the maximum degree. For the more general concept of $t$-tone coloring, we achieve similar results.

13 pages