### Abstract

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 language | English |
---|---|

Pages (from-to) | 1073-1086 |

Number of pages | 14 |

Journal | Graphs and Combinatorics |

Volume | 30 |

Issue number | 5 |

DOIs | |

Publication status | Published - Sep 2014 |

### Fingerprint

### Keywords

- Random graphs
- Tone colorings
- Vertex labelings

### Cite this

*Graphs and Combinatorics*,

*30*(5), 1073-1086. https://doi.org/10.1007/s00373-013-1341-9