Publications [#10385] of Mark Huber

Preprints

1. James A. Fill, Mark L. Huber, Linear expected time perfect generation of proper colorings of low degree graphs , preprint 2001
   (last updated on 2002/12/17)

   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.