A Lower Bound for the t-Tone Chromatic Number of a Graph in Terms of Wiener Index

作者：Pan Jun-Jie^*; Tsai Cheng-Hsiu

来源：Graphs and Combinatorics, 2018, 34(1): 159-162.

DOI：10.1007/s00373-017-1863-7

• t-Tone chromatic number
• Wiener index

A t-tone k-coloring of a graph is a function such that for all distinct vertices u and v. The t-tone chromatic number of G, denoted , 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 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.

• 出版日期2018-1