Timeline for Properties of the collection of maximal independent sets of a graph
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2019 at 0:35 | comment | added | Brendan McKay | 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$. | |
| Apr 16, 2019 at 19:17 | comment | added | Richard Stanley | 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. | |
| Apr 16, 2019 at 16:09 | comment | added | hbm | @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. | |
| Apr 16, 2019 at 16:05 | history | edited | hbm | CC BY-SA 4.0 |
added 67 characters in body
|
| Apr 16, 2019 at 2:03 | comment | added | LeechLattice | Something can be said about the size: $|\mathscr{I}(G)|\leq3^{|G|/3}$. | |
| Apr 16, 2019 at 0:44 | comment | added | Brendan McKay | 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. | |
| Apr 16, 2019 at 0:10 | history | asked | hbm | CC BY-SA 4.0 |