Sparse graphs usually have exponentially many optimal colorings (Q1601114)

Summary: 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.