Three remarks on ${\mathbf{W}}_2$ graphs

Abstract

Let $k\ge 1$. A graph $G$ is ${\mathbf{W}}_{\mathbf{k}}$ if for any $k$ pairwise disjoint independent vertex subsets $A_1,\dots ,A_k$ in $G$, there exist $k$ pairwise disjoint maximum independent sets $S_1,\dots ,S_k$ in $G$ such that $A_i\subseteq S_i$ for $i\in [k]$. Recognizing ${\mathbf{W}}_1$ graphs is co-NP-hard, as shown by Chvátal and Slater (1993) and, independently, by Sankaranarayana and Stewart (1992). Extending this result and answering a recent question of Levit and Tankus, we show that recognizing ${\mathbf{W}}_{\mathbf{k}}$ graphs is co-NP-hard for $k\ge 2$. On the positive side, we show that recognizing ${\mathbf{W}}_{\mathbf{k}}$ graphs is, for each $k\ge 2$, FPT parameterized by clique-width and by tree-width. Finally, we construct graphs $G$ that are not ${\mathbf{W}}_2$ such that, for every vertex $v$ in $G$ and every maximal independent set $S$ in $G-N[v]$, the largest independent set in $N(v)\setminus S$ consists of a single vertex, thereby refuting a conjecture of Levit and Tankus.

7 pages