2023/07/28 by Carl Feghali, Feghali, Carl, Malory Marin +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2307.15573
Let k ≥ 1. A graph G is Wk if for any k pairwise disjoint independent vertex subsets A1, …, Ak in G, there exist k pairwise disjoint maximum independent sets S1, …, Sk in G such that Ai ⊆ Si for i ∈ [k]. Recognizing W1 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 Wk graphs is co-NP-hard for k ≥ 2. On the positive side, we show that recognizing Wk graphs is, for each k≥ 2, FPT parameterized by clique-width and by tree-width. Finally, we construct graphs G that are not W2 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.