Let $G$ be a (simple) graph.

Given $k \ge \chi(G)$, define $Cor(G,k,u,v)$ to be the proportion among all $k$-colorings of $G$ for which the vertices $u$ and $v$ have the same color.

Questions:

Question 1. Given a graph $G$ and a positive integer $k \ge \chi(G)$, is there a better-than-greedy way to calculate $Cor(G,k,u,v)$?

I suspect the answer to this question is "Yes, but not really."; for is there was an efficient way to calculate $Cor$, we would probably get $P=NP$.

Question 2. If not, is there a ``good'' way to estimate it?

Question 3. Is there any other information (e.g., the chromatic polynomial, etc.) that would yield an efficient way to calculate $Cor$?