# Graph Colorings

A proper coloring of a graph ${\displaystyle G(V,E)}$ is a mapping ${\displaystyle f:V\rightarrow [q]}$ for some integer ${\displaystyle q}$, satisfying that ${\displaystyle f(u)\neq f(v)}$ for all ${\displaystyle uv\in E}$.

We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics.

Let's first consider the decision version of the problem. That is, given as input a graph ${\displaystyle G(V,E)}$, decide whether there exists a proper ${\displaystyle q}$-coloring of ${\displaystyle G}$. Denote by ${\displaystyle \Delta }$ the maximum degree of ${\displaystyle G}$.

• If ${\displaystyle q\geq \Delta +1}$, there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
• If ${\displaystyle q=\Delta }$, ${\displaystyle G}$ has a proper coloring unless it contains a ${\displaystyle (\Delta +1)}$-clique or it is an odd cycle. (Brooks Theorem)
• If ${\displaystyle q<\Delta }$, the problem is NP-hard.

Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when ${\displaystyle q<\Delta }$. The decision problem for the case ${\displaystyle q=\Delta }$ is also nontrivial. Thus people are interested only in the case when ${\displaystyle q\geq \Delta +1}$.

The following is a natural Markov chain for sampling proper colorings.

 Markov Chain for Graph Coloring ${\displaystyle {\mathcal {M}}_{c}}$ Start with a proper coloring of ${\displaystyle G(V,E)}$. At each step: Pick a vertex ${\displaystyle v\in V}$ and a color ${\displaystyle c\in [q]}$ uniformly at random. Change the color of ${\displaystyle v}$ to ${\displaystyle c}$ if the resulting coloring is proper; do nothing if otherwise.

For a fixed graph ${\displaystyle G(V,E)}$, the state space of the above Markov chain is the set of all proper colorings of ${\displaystyle G}$ with ${\displaystyle q}$ colors.

 Lemma The followings hold for ${\displaystyle {\mathcal {M}}_{c}}$. Aperiodic. The transition matrix is symmetric. Irreducible if ${\displaystyle q\geq \Delta +2}$.

The followings are the two most important conjectures regarding the problem.

 Conjecture ${\displaystyle {\mathcal {M}}_{c}}$ has mixing time ${\displaystyle O(n\ln n)}$ whenever ${\displaystyle q\geq \Delta +2}$. Random sampling of proper graph colorings can be done in polynomial time whenever ${\displaystyle q\geq \Delta +1}$.

These two conjectures are still open. People approach them by relax the requirement for the number of colors ${\displaystyle q}$. Intuitively, the larger the ${\displaystyle q}$ is, the more freedom we have, the less dependency are there between non-adjacent vertices.

# Coupling: ${\displaystyle q\geq 4\Delta +1}$

We couple the two copies of ${\displaystyle {\mathcal {M}}_{c}}$, ${\displaystyle X_{t}}$ and ${\displaystyle Y_{t}}$, by the following coupling rule:

• At each step, let ${\displaystyle X_{t}}$ and ${\displaystyle Y_{t}}$ choose the same vertex ${\displaystyle v}$ and same color ${\displaystyle c}$.

Note that by this coupling, it is possible that ${\displaystyle v}$ is recolored to ${\displaystyle c}$ in both chains, in one of the two chains, or in no chain. We may separate these cases by looking at the Hamming distance between two colorings.

Let ${\displaystyle d(X_{t},Y_{t})}$ be the number of vertices whose colors in ${\displaystyle X_{t}}$ and ${\displaystyle Y_{t}}$ disagree. For each step, for any choice of vertex ${\displaystyle v}$ and color ${\displaystyle c}$, there are three possible cases:

• "Good move" (${\displaystyle d(X_{t},Y_{t})}$ decreases by 1): ${\displaystyle X_{t}}$ disagree with ${\displaystyle Y_{t}}$ at ${\displaystyle v}$, and ${\displaystyle c}$ is not used in the colors of ${\displaystyle v}$ in both ${\displaystyle X_{t}}$ and ${\displaystyle Y_{t}}$.
• "Bad move" (${\displaystyle d(X_{t},Y_{t})}$ increases by 1):
• "Neutral move" (${\displaystyle d(X_{t},Y_{t})}$ is unchanged):