Polynomial-time recognition of relating edges in graphs with no 6-cycles

At least 7 years old · documented by

Let GG be a graph in G(C^6)\mathcal{G}(\widehat{C}_{6}), and let xy∈E(G)xy \in E(G) be an edge. The edge xyxy is called relating when it has the relating-edge property used in the paper.

Relating-edge recognition conjecture. The following problem is polynomially solvable: given a graph G∈G(C^6)G \in \mathcal{G}(\widehat{C}_{6}) and an edge xy∈E(G)xy \in E(G), determine whether xyxy is relating.

The conjecture is proposed as a common generalization of the paper's polynomial results for related graph classes. Its resolution is not given in the supplied text.

References

Primary source

David Tankus, “Recognizing Generating Subgraphs in Graphs without Cycles of Lengths 6 and 7”, arXiv:1808.10137 (2018).

Progress summary

Never refreshed

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.