Recognizing relating edges in graphs without cycles of length 6 (Q6964823)

A graph \(G\) is called well-covered if all its maximal independent sets are of the same cardinality. Let \(w : V(G)\rightarrow \mathbb{R}\) be a weight function. Then \(G\) is called \(w\)-well-covered if all its maximal independent sets are of the same weight. An edge \(xy \in E(G)\) is relating if there exists \(S \subseteq V(G)\) such that both \(S \cup \{x\}\) and \(S \cup \{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 of whether an edge is relating is NP-complete. The authors prove that this problem remains NP-complete even for graphs without cycles of length 6. A graph \(G\) is said to belong to the class \(W_2\) if every two pairwise disjoint independent sets in \(G\) are included in two pairwise disjoint maximum independent sets. A vertex \(v \in V(G)\) is called shedding if for every independent set \(S \subseteq V(G) \backslash N[v]\) there exists \(u \in N(v)\) such that \(S\cup \{u\}\) is independent. Shedding vertices play an important role in studying the class \(W_2\), and recognizing shedding vertices is co-NP-complete. It was proved that this problem is co-NP-complete even for graphs without cycles of length 6. A conjecture concludes the paper.