Polynomial-time computation of the well-covered weight space for graphs with no 6- or 7-cycles
Polynomial-time computation of the well-covered weight space for graphs with no 6- or 7-cycles
Let be a graph in . The notation denotes the vector space of all weight functions such that is -well-covered.
Polynomial-time computation conjecture. The following problem can be solved in polynomial time: given a graph , output .
The authors motivate this conjecture by noting that enumerating all induced complete bipartite subgraphs can require exponential time. The paper proves polynomial-time recognition of generating subgraphs in this graph class, but leaves computation of the full well-covered weight space open.
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
David Tankus, “Recognizing Generating Subgraphs in Graphs without Cycles of Lengths 6 and 7”, arXiv:1808.10137 (2018).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.