Three remarks on 𝐖_2 graphs

07/28/2023

∙

by   Carl Feghali, et al.

∙

0

∙

share

Let k ≥ 1. A graph G is 𝐖_𝐤 if for any k pairwise disjoint independent vertex subsets A_1, …, A_k in G, there exist k pairwise disjoint maximum independent sets S_1, …, S_k in G such that A_i ⊆ S_i for i ∈ [k]. Recognizing 𝐖_1 graphs is co-NP-hard, as shown by Chvátal and Hartnell (1993) and, independently, by Sankaranarayana and Stewart (1992). Extending this result and answering a recent question of Levit and Tankus, we show that recognizing 𝐖_𝐤 graphs is co-NP-hard for k ≥ 2. On the positive side, we show that recognizing 𝐖_𝐤 graphs is, for each k≥ 2, FPT parameterized by clique-width and by tree-width. Finally, we construct graphs G that are not 𝐖_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) ∖ S consists of a single vertex, thereby refuting a conjecture of Levit and Tankus.