Enumerating maximal independent sets with applications to graph colouring |
| |
| Authors: | Jesper Makholm Byskov |
| |
| Affiliation: | BRICS22Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation., Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, DK-8200 Aarhus N, Denmark |
| |
| 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. |
| |
| Keywords: | Maximal independent set Graph colouring Chromatic number Graph algorithms Extremal graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
