# Properties of the collection of maximal independent sets of a graph

Let $$G$$ be a graph and define

$$\mathscr{I}(G) = \{S \subset V(G)| S$$ is a maximal indepedent set of $$G\}$$

1. What is known about $$\mathscr{I}(G)$$?

1. What are some of the properties of $$\mathscr{I}(G)$$?

2. How does $$\mathscr{I}(G)$$ relates to other properties of $$G$$ for example chromatic number?

3. Is it possible to decide if a collection $$\mathscr{A}$$ is equal to $$\mathscr{I}(H)$$ for some graph $$H$$( is there a set of conditions on $$\mathscr{A}$$ to tell)?

• 1 and 2 seem to be the same. For 3 it is clear that the chromatic number (in fact, the chromatic polynomial) is a function of $\mathscr{I}(G)$. Question 4 is easy: make the graph whose edges are the pairs of vertices that don't lie in the same member of $\mathscr{I}(G)$ and check that the independent sets are maximal. – Brendan McKay Apr 16 at 0:44
• Something can be said about the size: $|\mathscr{I}(G)|\leq3^{|G|/3}$. – Bullet51 Apr 16 at 2:03
• @BrendanMcKay, can you please elaborate on your comments about point 3. As for 4, I am more interested in a characterization ( a set of condition on the collection to tell) not the algorithmic aspect. – hbm Apr 16 at 16:09
• For 4, we may assume that no element of $\mathcal{A}$ is a subset of some other element. It is necessary and sufficient for $\mathcal{A}=\mathcal{I}(G)$ (for some $G$) that every minimal set of vertices not contained in some element of $\mathcal{A}$ has two elements. Although this is little more than a restatement of the definition of $\mathcal{I}(G)$, I doubt whether one can do better. – Richard Stanley Apr 16 at 19:17
• For 3, the chromatic number equals the least number of maximal independent sets that cover everything. It's just the definition of $\chi(G)$ without mentioning $G$. – Brendan McKay Apr 17 at 0:35