Correlation in graph coloring

Question

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

Answer 1

As regards question 3: Chromatic polynomials provide the answer quite directly--but calculating them is anything but efficient.

Naturally if $u$ and $v$ are joined by an edge, the proportion you are asking about is 0. If they are not adjacent, then let $q$ be the chromatic polynomial of $G$ and $p$ be the chromatic polynomial of $G/\{u,v\}$, i.e. the result of identifying $u$ and $v$. The proportion you seek is then the rational function $p/q$ evaluated at $k$, which as you point out is only defined for $k$ at least the chromatic number.

Answer 2

Question 1. Yes, efficient algorithm for Cor exists for graphs of low tree-width

Cast this in the framework of probabilistic graphical models and then use the junction tree algorithm, which scales exponentially in tree-width of the graph.

In particular, let $G$ be a graph over $n$ vertices with edges $E$. Let $x \in [1,2,\ldots, k]^n$. Define probability distribution over $x$ as follows

$$p(x)=\exp{(\sum_{(ij)\in E} \mathbf{I}(x_i\ne x_j))}/Z$$

Where $Z$ is a constant chosen to make this a valid probability distribution. Then $$\text{Cor}(G,k,u,v)=\sum_{c=1}^k p(x_u=c,x_v=c)$$

Computing p in the formula above in graphs that are not trees is not trivial, but can be done efficiently if the tree-width is low, look at page 370 of Koller's "Probabilistic Graphical Models" for details on that particular form of query.

Question 2. Yes, for graphs with low degree or large number of colors. For instance, here the authors conjecture that colorings on graphs with degree at most k and at least k+1 number of colors exhibits "strong spatial mixing", which would imply that the algorithm they give to approximate the marginals could also give a guaranteed approximation to your problem in polynomial time