0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Apr 16, 2019 at 0:44
  • $\begingroup$ Something can be said about the size: $|\mathscr{I}(G)|\leq3^{|G|/3}$. $\endgroup$
    – LeechLattice
    Commented Apr 16, 2019 at 2:03
  • $\begingroup$ @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. $\endgroup$
    – hbm
    Commented Apr 16, 2019 at 16:09
  • $\begingroup$ 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. $\endgroup$
    – Richard Stanley
    Commented Apr 16, 2019 at 19:17
  • $\begingroup$ 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$. $\endgroup$
    – Brendan McKay
    Commented Apr 17, 2019 at 0:35

0

Reset to default

You must log in to answer this question.