Abstract
A t-tone k-coloring of a graph \(G=(V,E)\) is a function \(f:V\rightarrow {[k] \atopwithdelims ()t}\) such that \(|f(u)\cap f(v)|<d(u,v)\) for all distinct vertices u and v. The t-tone chromatic number of G, denoted \(\tau _t(G)\), is the smallest positive integer k such that G has a t-tone k-coloring. The Wiener index W(G) of a connected graph G is the sum of the distances of all pairs of vertices of G. In this paper, we prove that \(\tau _t(G)\ge t|V|-W(G)+{|V|\atopwithdelims ()2}\) for a connected graph G and obtain a characterization when the equality holds. As a result, for each graph G (not necessarily connected), we obtain a formula for the t-tone chromatic number of G when t is sufficiently large.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bal, D., Bennett, P., Dudek, A., Frieze, A.: The \(t\)-tone chromatic number of random graphs. Gr. Combin. 30, 383–385 (2014)
Bickle, A., Phillips, B.: \(t\)-tone coloring of graphs (Submitted) (2011)
Cranston, D.W., Kim, J., Kinnersley, W.B.: New results in \(t\)-tone coloring of graphs. Electron. J. Combin. 20(2), 17 (2013)
Acknowledgements
The authors thank referees for many constructive suggestions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pan, JJ., Tsai, CH. A Lower Bound for the t-Tone Chromatic Number of a Graph in Terms of Wiener Index. Graphs and Combinatorics 34, 159–162 (2018). https://doi.org/10.1007/s00373-017-1863-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1863-7