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

Kritika Bhandari, Mark Huber

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…