The t-Tone Chromatic Number of Random Graphs

<p>A proper 2-tone <em>k</em>-coloring of a graph is a labeling of the vertices with elements from ([k]2) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph <em>G</em>, denoted <em>τ</em> 2(<em>G</em>) is the smallest <em>k</em> such that<em>G</em> admits a proper 2-tone <em>k</em> coloring. In this paper, we prove that w.h.p. for p≥Cn−1/4ln9/4n,τ2(Gn,p)=(2+o(1))χ(Gn,p) where χ represents the ordinary chromatic number. For sparse random graphs with <em>p</em> = <em>c</em>/<em>n</em>, <em>c</em> constant, we prove that τ2(Gn,p)=⌈(8Δ+1−−−−−−√+5)/2 where Δ represents the maximum degree. For the more general concept of <em>t</em>-tone coloring, we achieve similar results.</p>