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

About 3 years old · traced to

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 v∈V(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.