Recognizing Relating Edges in Graphs without Cycles of Length 6

A graph G is well-covered if all maximal independent sets are of the same cardinality. Let w:V(G) be a weight function. Then G is w-well-covered if all maximal independent sets are of the same weight. An edge xy ∈ E(G) is relating if there exists an independent set S such that both S ∪ \ and S ∪ \ are maximal independent sets in the graph. If $xy$ is relating then $w(x)=w(y)$ for every weight function w such that G is w-well-covered. Relating edges play an important role in investigating w-well-covered graphs. The decision problem whether an edge in a graph is relating is NP-complete. We prove that the problem remains NP-complete when the input is restricted to graphs without cycles of length $6$. This is an unexpected result because recognizing relating edges is known to be polynomially solvable for graphs without cycles of lengths $4$ and $6$, graphs without cycles of lengths $5$ and $6$, and graphs without cycles of lengths $6$ and $7$. A graph G belongs to the class W₂ if every two pairwise disjoint independent sets in G are included in two pairwise disjoint maximum independent sets. It is known that if G belongs to the class W₂, then it is well-covered. A vertex v ∈ V(G) is shedding if for every independent set S ⊆ V(G)-N[v], there exists a vertex u ∈ N(v) such that S ∪ \ is independent. Shedding vertices play an important role in studying the class W₂. Recognizing shedding vertices is co-NP-complete, even when the input is restricted to triangle-free graphs. We prove that the problem is co-NP-complete for graphs without cycles of length $6$.