๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Enumerating maximal independent sets with applications to graph colouring

โœ Scribed by Jesper Makholm Byskov

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
246 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

Maximal independent sets in graphs with
Maximal independent sets in graphs with at most r cycles
โœ Goh Chee Ying; Koh Khee Meng; Bruce E. Sagan; Vincent R. Vatter ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 127 KB ๐Ÿ‘ 2 views

## Abstract We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with __n__ vertices and at most __r__ cycles. The second family is all graphs of the first family which are connected and satisfy __n__โ€‰โ‰ฅโ€‰3__r__. ยฉ 2006 Wiley Period

Maximal independent sets in graphs with
Maximal independent sets in graphs with at most one cycle
โœ Min-Jen Jou; Gerard J. Chang ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 356 KB

In this paper, we determine the largest number of maximal independent sets among all connected graphs of order n, which contain at most one cycle. We also characterize those extremal graphs achieving this maximum value. As a consequence, the corresponding results for graphs with at most one cycle bu

Maximal and maximum independent sets in
Maximal and maximum independent sets in graphs with at most r cycles
โœ Bruce E. Sagan; Vincent R. Vatter ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 236 KB ๐Ÿ‘ 2 views

## Abstract Let __m__(__G__) denote the number of maximal independent sets of vertices in a graph __G__ and let __c__(__n__,__r__) be the maximum value of __m__(__G__) over all connected graphs with __n__ vertices and at most __r__ cycles. A theorem of Griggs, Grinstead, and Guichard gives a formul

A characterization of graphs of girth ei
A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets
โœ A. Finbow; B. Hartnell; C. Whitehead ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 1003 KB

In 1970, Plummer introduced the notion of a well-covered graph as one in which every maximal independent set is a maximum. Here, we study graphs in which there are exactly two sizes of maximal independent sets. A characterization of such graphs is obtained for graphs of girth eight or more.