The minimum maximal-independent-set conjecture for connected twin-free triangle-free graphs
Let be a connected, twin-free and triangle-free graph of order . Write for the number of maximal independent sets of . Minimum maximal-independent-set conjecture.
Furthermore, if 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.
References
Primary source
Stijn Cambie and Stephan Wagner, “The minimum number of maximal independent sets in twin-free graphs”, arXiv:2211.04357 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.