Polynomial-time recognition of relating edges in graphs with no 6-cycles
Let be a graph in , and let be an edge. The edge 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 and an edge , determine whether 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.