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.
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$?