Polynomial-time computation of the well-covered weight space for graphs with no 6- or 7-cycles

From papers

Let GG be a graph in G(C^6,C^7)\mathcal{G}(\widehat{C}_{6},\widehat{C}_{7}). The notation WCW(G)WCW(G) denotes the vector space of all weight functions ww such that GG is ww-well-covered.

Polynomial-time computation conjecture. The following problem can be solved in polynomial time: given a graph GG(C^6,C^7)G \in \mathcal{G}(\widehat{C}_{6},\widehat{C}_{7}), output WCW(G)WCW(G).

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

No solutions have been posted yet.