Levit–Tankus characterization conjecture for \mathbf{W_2} graphs

Let GG be a graph. For a vertex vv, let N(v)N(v) denote its open neighborhood and let N[v]N[v] denote its closed neighborhood. Write GN[v]G-N[v] for the graph obtained by deleting vv and its neighbors, and for a set SS write N(S)N(S) for its neighborhood. A set of vertices is independent if no two of its vertices are adjacent, and it is maximal independent if it is not properly contained in a larger independent set.

Levit–Tankus conjecture. The graph GG is W2\mathbf{W_2} if and only if, for every vertex vv in GG and every maximal independent set SS in GN[v]G-N[v], the largest independent set in N(v)N(S)N(v)\setminus N(S) consists of a single vertex.

The paper states this as a proposed characterization of W2\mathbf{W_2} graphs and refutes it in the cited work, so the claim is not valid in general.

Sources & referencesView supporting material

Primary source

Carl Feghali and Malory Marin, “Three remarks on W_2 graphs”, arXiv:2307.15573 (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.