Entropy and a certain cost-minimal coloring of graph vertices (Q2472782)

Let \(G\) be a graph with \(n\) vertices and \(m\) edges and let \(c:V(G)\to\{1,2,\dots,n\}\) be a vertex coloring. We first view \(i\) as the cost associated with color \(i\) and consider the minimum total cost \(t(G)= \min_c \sum_{x\in 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/2^{H(\overline{G})}+ 1)/2\leq t(G)/n\). (\(\overline{G}\) is the complement of \(G\).) Using \(g(G)/n\leq m/n+1\), we have \(\log(n^2/(n^2-2m))\leq 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.