The characterization of graphs by neighborhood independence
The characterization of graphs by neighborhood independence
Let be a graph, let denote its vertex set, let and denote the open and closed neighborhoods of a vertex , let denote the neighborhood of a vertex set , and let denote the independence number. The class is the class of graphs whose independent sets can be extended to independent sets of maximum cardinality in the relevant induced subgraphs.
characterization conjecture. For every graph , the following assertions are equivalent:
- is in the class .
- for every vertex and for every maximal independent set of .
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
Sign in to submit a solution.
No solutions have been posted yet.