The minimum maximal-independent-set conjecture for connected twin-free triangle-free graphs

From papers

Let GG be a connected, twin-free and triangle-free graph of order nn. Write imax(G)i_{\text{max}}(G) for the number of maximal independent sets of GG. Minimum maximal-independent-set conjecture.

imax(G)n2+1.i_{\text{max}}(G) \ge \left\lceil\frac{n}{2}\right\rceil+1.

Furthermore, if nn is even, every graph attaining equality is bipartite. The preceding theorem proves this bound for connected twin-free bipartite graphs, while the extension to triangle-free graphs is presented as unproved; the equality characterization is likewise part of the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Stijn Cambie and Stephan Wagner, “The minimum number of maximal independent sets in twin-free graphs”, arXiv:2211.04357 (2024).

Solutions 0

No solutions have been posted yet.