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 \( \Delta \) when the number of colors is greater than \( 3.637 \Delta + 1\).
Related papers
Ranked by semantic similarity β how closely each paper's abstract matches this one (100% = near-identical topic).