The characterization of W2\mathbf{W_2} graphs by neighborhood independence

From papers

Let GG be a graph, let V(G)V(G) denote its vertex set, let N(v)N(v) and N[v]N[v] denote the open and closed neighborhoods of a vertex vv, let N(S)N(S) denote the neighborhood of a vertex set SS, and let α\alpha denote the independence number. The class W2\mathbf{W_2} is the class of graphs whose independent sets can be extended to independent sets of maximum cardinality in the relevant induced subgraphs.

W2\mathbf{W_2} characterization conjecture. For every graph GG, the following assertions are equivalent:

  1. GG is in the class W2\mathbf{W_2}.
  2. α(N(v)N(S))=1\alpha(N(v) \setminus N(S)) = 1 for every vertex vV(G)v \in V(G) and for every maximal independent set SS of V(G)N[v]V(G) \setminus N[v].

The equivalence is proved in the source for well-covered graphs; the conjecture asks whether the same characterization holds for arbitrary graphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Vadim E. Levit and David Tankus, “Recognizing W_2 Graphs”, arXiv:2306.17272 (2023).

Solutions 0

No solutions have been posted yet.