Coloring entropy weight ($w(G)=|V(G)|{\min }_{\chi }H(\chi (Z))$)

For a uniformly chosen vertex $Z$, minimize the information entropy of its color over proper colorings. Multiply by the number of vertices to define this weight. Minimizing the color entropy gives the strongest contribution from that graph in the entropy weight of a graph cover inequality.

If graphs $G_i$ cover the edges of an $n$-vertex graph with independence number at most $\alpha$, their coloring entropy weights satisfy the displayed bound. A random vertex's color is recorded in every covering graph containing it; independent dummy colors with matching marginal laws fill the other positions. Conditional on all recorded colors, compatible vertices form an independent set, leaving conditional entropy at most ${\log }_2\alpha$. The mutual information carried by the colors is at most $n^{-1}{\sum }_{i}w(G_i)$, proving the bound.