Recognizing Relating Edges in Graphs Without Cycles of Length 6

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Let w:V(G)⟶R be a weight function. Then G is w-well-covered if all its maximal independent sets are of the same weight. An edge xy∈E(G) is relating if there exists S⊆V(G) such that both S∪{x} and S∪{y} are maximal independent sets. If xy is relating then w(x)=w(y) for every weight function w such that G is w-well-covered. Relating edges are of crucial importance for investigating w-well-covered graphs. The problem whether an edge is relating is NP-complete. We prove that this problem remains NP-complete even for graphs without cycles of length 6. A graph G belongs to the class W2 if every two pairwise disjoint independent sets in G are included in two pairwise disjoint maximum independent sets. A vertex v∈V(G) is shedding if for every independent set S⊆V(G)\N[v] there exists u∈N(v) such that S∪{u} is independent. Shedding vertices play an important role in studying the class W2. Recognizing shedding vertices is co-NP-complete. We prove that this problem is co-NP-complete even for graphs without cycles of length 6.