Small Maximal Independent Sets and Faster Exact Graph Coloring

Simple item page
dc.creatorEppstein, David
dc.date2000-11-06
dc.date.accessioned2026-07-07T03:16:41Z
dc.date.available2026-07-07T03:16:41Z
dc.descriptionWe show that, for any n-vertex graph G and integer parameter k, there are at most 3^{4k-n}4^{n-3k} maximal independent sets I \subset G with |I| <= k, and that all such sets can be listed in time O(3^{4k-n} 4^{n-3k}). These bounds are tight when n/4 <= k <= n/3. As a consequence, we show how to compute the exact chromatic number of a graph in time O((4/3 + 3^{4/3}/4)^n) ~= 2.4150^n, improving a previous O((1+3^{1/3})^n) ~= 2.4422^n algorithm of Lawler (1976).
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/cs/0011009
dc.identifierhttp://arxiv.org/abs/cs/0011009
dc.identifierJ. Graph Algorithms & Applications 7(2):131-140, 2003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30449
dc.subjectData Structures and Algorithms
dc.subjectCombinatorics
dc.subjectF.2.2
dc.titleSmall Maximal Independent Sets and Faster Exact Graph Coloring
dc.typetext

Files

Collections

arXiv