We prove a number of results related to the computational complexity of recognizing well-covered graphs. For instance, let k and s be positive integers and G be a graph. Then G is said Chvátal and Slater (1993) and Sankaranarayana and Stewart (1992) famously showed that recognizing \(\mathbf {W_1}\) graphs or, equivalently, well-covered graphs is coNP-complete. We extend this result by showing that recognizing \(\mathbf {W_{k+1}}\) graphs in either \(\mathbf {W_k}\) or \(\mathbf {E_s}\) graphs is coNP-complete. This answers a question of Levit and Tankus (2023) and strengthens a theorem of Feghali and Marin (2024). We also show that recognizing \(\mathbf {E_{s+1}}\) graphs is \(\varTheta _2^p\) -complete even in \(\mathbf {E_s}\) graphs, where \(\varTheta _2^p = \text {P}^{\text {NP}[\log ]}\) is the class of problems solvable in polynomial time using a logarithmic number of calls to a Sat oracle. This strengthens a theorem of Bergé, Busson, Feghali and Watrigant (2023). We also obtain the complete picture of the complexity of recognizing chordal \(\mathbf {W_k}\)  and \(\mathbf {E_s}\) graphs which, in particular, simplifies and generalizes a result of Dettlaff, Henning and Topp (2023).