Sparse Graphs Usually Have Exponentially Many Optimal Colorings

Abstract

A proper coloring of a graph $G=(V,E)$ is called optimal if the number of colors used is the minimal possible; i.e., it coincides with the chromatic number of $G$.

We investigate the typical behavior of the number of distinct optimal colorings of a random graph $G(n,p)$, for various values of the edge probability $p=p(n)$. Our main result shows that for every constant $1/3 < a < 2$, most of the graphs in the probability space $G(n,p)$ with $p=n^{-a}$ have exponentially many optimal colorings.