The minimum maximal-independent-set conjecture for connected twin-free triangle-free graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.