We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The t-Tone Chromatic Number of Random Graphs.
- Authors
Bal, Deepak; Bennett, Patrick; Dudek, Andrzej; Frieze, Alan
- Abstract
A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from $${\binom{[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 τ( 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\geq Cn^{-1/4} {\rm 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}}}$$ where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.
- Subjects
RANDOM graphs; GRAPH coloring; GRAPH labelings; SPARSE matrices; MATHEMATICAL proofs
- Publication
Graphs & Combinatorics, 2014, Vol 30, Issue 5, p1073
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-013-1341-9