Beyond recognizing well-covered graphs

We prove a number of results related to the computational complexity of recognizing well-covered graphs. Let k and s be positive integers and let G be a graph. Then G is said - Wₖ if for any k pairwise disjoint independent vertex sets A₁, , Aₖ in G, there exist k pairwise disjoint maximum independent sets S₁, ,Sₖ in G such that Aᵢ ⊆ Sᵢ for i ∈ [k]. - Eₛ if every independent set in G of size at most s is contained in a maximum independent set in G. Chv\'atal and Slater (1993) and Sankaranarayana and Stewart (1992) famously showed that recognizing W₁ graphs or, equivalently, well-covered graphs is coNP-complete. We extend this result by showing that recognizing Wₖ₊₁ graphs in either Wₖ or Eₛ 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 Eₛ₊₁ graphs is Θ₂ᵖ-complete even in Eₛ graphs, where Θ₂ᵖ = PNP[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\'e, Busson, Feghali and Watrigant (2023). We also obtain the complete picture of the complexity of recognizing chordal Wₖ and Eₛ graphs which, in particular, simplifies and generalizes a result of Dettlaff, Henning and Topp (2023).