Polynomial-time recognition of relating edges in graphs with no 6-cycles
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.
Sources & referencesView supporting material
Primary source
David Tankus, “Recognizing Generating Subgraphs in Graphs without Cycles of Lengths 6 and 7”, arXiv:1808.10137 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.