{
  "id": "2307.15573",
  "version": "v1",
  "published": "2023-07-28T14:12:22.000Z",
  "updated": "2023-07-28T14:12:22.000Z",
  "title": "Three remarks on $\\mathbf{W_2}$ graphs",
  "authors": [
    "Carl Feghali",
    "Malory Marin"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $k \\geq 1$. A graph $G$ is $\\mathbf{W_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\\'atal 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 $\\mathbf{W_k}$ graphs is co-NP-hard for $k \\geq 2$. On the positive side, we show that recognizing $\\mathbf{W_k}$ graphs is, for each $k\\geq 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-28T14:12:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "pairwise disjoint maximum independent sets",
      "pairwise disjoint independent vertex subsets",
      "maximal independent set",
      "largest independent set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}