Strongly minimal covers by independent sets
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.
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
Ron Aharoni, Eli Berger, Agelos Georgakopoulos and Philipp Sprüssel, “Strongly maximal matchings in infinite weighted graphs”, arXiv:0911.4010 (2009).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.