Enumerating maximal independent sets with applications to graph colouring

Enumerating maximal independent sets with applications to graph colouring

0.00 Avg rating—0 Votes
Article ID: iaor2005705
Country: Netherlands
Volume: 32
Issue: 6
Start Page Number: 547
End Page Number: 556
Publication Date: Nov 2004
Journal: Operations Research Letters
Authors:
Keywords: sets
Abstract:

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.

Reviews

Required fields are marked *. Your email address will not be published.