Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph

A new algorithm for exactly sampling from the set of proper colorings of a graph is presented. This is the first such algorithm that has an expected running time that is guaranteed to be linear in the size of a graph with maximum degree $\mathrm{\Delta }$ when the number of colors is greater than $3.637\mathrm{\Delta }+1$.