The t-Tone Chromatic Number of Random Graphs

Deepak Bal, Patrick Bennett, Andrzej Dudek, Alan Frieze

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from (formula presented.) 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 that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for (formula presented.) where X represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that (formula presented.) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.

Original languageEnglish
Pages (from-to)1073-1086
Number of pages14
JournalGraphs and Combinatorics
Issue number5
StatePublished - Sep 2014


  • Random graphs
  • Tone colorings
  • Vertex labelings


Dive into the research topics of 'The t-Tone Chromatic Number of Random Graphs'. Together they form a unique fingerprint.

Cite this