Entropy and a certain cost-minimal coloring of graph vertices

AbstractLet G be a graph with n vertices and m edges and let c:V(G)→{1,2,…,n} be a vertex coloring. We first view i as the cost associated with color i and consider the minimum total cost t(G)=minc∑x∈V(G)c(x). An inequality relation between t(G) and the minimum entropy H(G) of the color distribution induced by any coloring is obtained as (n/2H(G¯)+1)/2⩽t(G)/n. (G¯ is the complement of G.) Using t(G)/n⩽m/n+1, we have log(n2/(n2−2m))⩽H(G), and the standard argument of entropy maximization leads to a lower bound on t(G)/n in terms of n,m only. Finally, it is remarked that the results can be extended to a case of more general costs