Math @ Duke

Publications [#10385] of Mark Huber
Preprints
 James A. Fill, Mark L. Huber, Linear expected time perfect generation of proper colorings of low degree graphs
(2008)
(last updated on 2008/08/18)
Abstract: A proper coloring assigns colors to nodes of a graph so
that no two endpoints of an edge receive the same color.
Here we present the first algorithm for sampling uniformly
from the set of proper colorings of a graph (in expected
linear time) when the number of colors is linear in the
maximum degree of the graph.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

