English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $k \geq 1$. A graph $G$ is $\mathbf{W_k}$ if for any $k$ pairwisedisjoint 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 isco-NP-hard, as shown by Chv\'atal and Slater (1993) and, independently, bySankaranarayana and Stewart (1992). Extending this result and answering arecent question of Levit and Tankus, we show that recognizing $\mathbf{W_k}$graphs is co-NP-hard for $k \geq 2$. On the positive side, we show thatrecognizing $\mathbf{W_k}$ graphs is, for each $k\geq 2$, FPT parameterized byclique-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 maximalindependent set $S$ in $G - N[v]$, the largest independent set in $N(v)\setminus S$ consists of a single vertex, thereby refuting a conjecture ofLevit and Tankus.

Three remarks on $\mathbf{W_2}$ graphs