<p>The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices connected by an edge). I am interested in a related quantity. In my problem, I am given a probability distribution $P$ on the vertices of $G$ and I am interested in minimizing the (Shannon) entropy of the induced probability distribution on the colors over all proper colorings of the vertices of $G.$ Let this quantity be denoted by $\rho(G,P).$ We have trivially,</p>

<p>$$\rho(G,P)\leq \log_2\chi(G).$$</p>

<p>Note that the entropy minimizing coloring need not use the minimum possible number of colors. Eg. Consider a 6-cycle with probabilities 0.48,0.01,0.01,0.48,0.01,0.01 in that order. The three-coloring that pairs the two heavy diametrically opposite points will have a lower entropy than any two-coloring.</p>

<p>More generally, I want to understand what happens when one considers tensor powers of the graph. Consider the AND product of graphs where an edge exists between $(v_1,v_2)$ and $(w_1,w_2)$ if and only if there exist edges $(v_1,w_1)$ and $(v_2,w_2)$ or if $v_1=w_1$ and $(v_2,w_2)$ is an edge or if $v_2=w_2$ and $(v_1,w_1)$ is an edge. It is easy to show that the sequence $\chi(G^{\otimes n})$ is sub-multiplicative and so the limit $\lim_{n\to\infty}\chi(G^{\otimes n})^{\frac{1}{n}}$ exists (sometimes called Witsenhausen's rate of $G$). An analogous quantity for $\rho$ may be defined as below and existence of the limit follows from subadditivity again:</p>

<p>$$\lim_{n\to\infty} \frac{\rho(G^{\otimes n},P^{\otimes n})}{n}.$$</p>

<p>Note here we also take the tensor product of the specified probability distribution $P$. Do we know anything about these quantities? Any related references would be useful. Thanks!</p>

CC BY-SA 3.0
2014-10-12T09:53:04.547Z
Unless I am mistaken, in the definition of the product of graphs, I think that you need an edge also in the case where v_1=w_1 and (v_2,w_2) is an edge and in the case where (v_1,w_1) is an edge and v_2=w_2.  Otherwise I think χ(G^⊗n) would be equal to χ(G).
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-12T09:55:54.470Z
I think that submultiplicativity can be shown exactly in the same way as in the case of chromatic number and that therefore the limit in question always exists…or am I missing something?
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-14T03:01:07.020Z
Just a clarification: Is the question asking about the limit tensor products or about minimum entropy coloring in general?  Is there an easy example of a specific graph, $G$, and a distribution where a minimum entropy coloring uses more than $\chi(G)$ colors?
Pat Morin
CC BY-SA 3.0
2014-10-14T12:56:21.243Z
Pat: Yes, the question is about minimum entropy coloring in general. I want to know if there is such an example. Thanks.
user7823
CC BY-SA 3.0
2014-10-14T15:08:13.273Z
Pat: I found a simple example showing the minimum entropy coloring may use more colors than the chromatic number. I included it in the question.
user7823
<graph-theory>
The minimum entropy of a proper coloring of a graph
user7823
# The minimum entropy of a proper coloring of a graph

(Asked by: username_0 on 2014-10-10)

The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices connected by an edge). I am interested in a related quantity. In my problem, I am given a probability distribution $P$ on the vertices of $G$ and I am interested in minimizing the (Shannon) entropy of the induced probability distribution on the colors over all proper colorings of the vertices of $G.$ Let this quantity be denoted by $\rho(G,P).$ We have trivially,

$$\rho(G,P)\leq \log\_2\chi(G).$$

Note that the entropy minimizing coloring need not use the minimum possible number of colors. Eg. Consider a 6-cycle with probabilities 0.48,0.01,0.01,0.48,0.01,0.01 in that order. The three-coloring that pairs the two heavy diametrically opposite points will have a lower entropy than any two-coloring.

More generally, I want to understand what happens when one considers tensor powers of the graph. Consider the AND product of graphs where an edge exists between $(v\_1,v\_2)$ and $(w\_1,w\_2)$ if and only if there exist edges $(v\_1,w\_1)$ and $(v\_2,w\_2)$ or if $v\_1=w\_1$ and $(v\_2,w\_2)$ is an edge or if $v\_2=w\_2$ and $(v\_1,w\_1)$ is an edge. It is easy to show that the sequence $\chi(G^{\otimes n})$ is sub-multiplicative and so the limit $\lim\_{n\to\infty}\chi(G^{\otimes n})^{\frac{1}{n}}$ exists (sometimes called Witsenhausen's rate of $G$). An analogous quantity for $\rho$ may be defined as below and existence of the limit follows from subadditivity again:

$$\lim\_{n\to\infty} \frac{\rho(G^{\otimes n},P^{\otimes n})}{n}.$$

Note here we also take the tensor product of the specified probability distribution $P$. Do we know anything about these quantities? Any related references would be useful. Thanks!

**Tags:** graph-theory
> **Comments:**
> **username_1**: Unless I am mistaken, in the definition of the product of graphs, I think that you need an edge also in the case where v_1=w_1 and (v_2,w_2) is an edge and in the case where (v_1,w_1) is an edge and v_2=w_2.  Otherwise I think χ(G^⊗n) would be equal to χ(G).  
> **username_1**: I think that submultiplicativity can be shown exactly in the same way as in the case of chromatic number and that therefore the limit in question always exists…or am I missing something?  
> **username_2**: Just a clarification: Is the question asking about the limit tensor products or about minimum entropy coloring in general?  Is there an easy example of a specific graph, $G$, and a distribution where a minimum entropy coloring uses more than $\chi(G)$ colors?  
> **username_0**: Pat: Yes, the question is about minimum entropy coloring in general. I want to know if there is such an example. Thanks.  
> **username_0**: Pat: I found a simple example showing the minimum entropy coloring may use more colors than the chromatic number. I included it in the question.  

---

## 0 answers

