Strongly minimal covers by independent sets
Let be a graph. An independent set is a set of vertices containing no edge of , and a cover of the vertex set is a family of such sets whose union is the vertex set. Strong minimality is the dual notion to strong maximality: a cover is strongly minimal when it is no larger, in the corresponding cardinal comparison, than any alternative cover. Strongly minimal cover conjecture. Every graph has a strongly minimal cover of its vertex set by independent sets. A positive answer would yield further consequences for posets of bounded width, while the existence of such covers remains open in the stated generality.
References
- Ron Aharoni, Eli Berger, Agelos Georgakopoulos and Philipp Sprüssel, “Strongly maximal matchings in infinite weighted graphs”, arXiv:0911.4010 (2009).
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.