Skip to main content
1 of 2
hbm
  • 1k
  • 7
  • 14

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)$?

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

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

  4. Is it possible to decide if a collection $\mathscr{A}$ is equal to $\mathscr{I}(H)$ for some graph $H$?

hbm
  • 1k
  • 7
  • 14