首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Enumerating maximal independent sets with applications to graph colouring
Authors:Jesper Makholm Byskov
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号