Carnegie Mellon University
file.pdf (172.46 kB)

The t-Tone Chromatic Number of Random Graphs

Download (172.46 kB)
journal contribution
posted on 2013-03-06, 00:00 authored by Deepak Bal, Patrick Bennett, Andrzej Dudek, Alan FriezeAlan Frieze

A proper 2-tone k-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 G, denoted τ 2(G) is the smallest k such thatG admits a proper 2-tone k 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 p = c/n, c constant, we prove that τ2(Gn,p)=⌈(8Δ+1−−−−−−√+5)/2 where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.


Publisher Statement

The final publication is available at Springer via



Usage metrics