Graph Coloring and Conditional Graph Entropy

The authors consider the remote computation of a function of two sources where one is receiver side information. Specifically, given side information Y, they wish to compute f(X, Y) based on information transmitted by X over a noise-less channel. The goal is to characterize the minimal rate at which X must transmit information to enable the computation of the function f. They establish that a minimum (conditional) entropy coloring of the product of characteristic graphs is asymptotically equal to the conditional graph entropy. This can be seen as a generalization of a result of Korner (1973) which shows that the minimum entropy coloring of product graphs is asymptotically equal to the graph entropy.