← All problems

Zaare-Nahandi's semi-perfectness conjecture for multipartite well-covered graphs

9 years old · documented by

Let GG be an ss-partite well-covered graph, meaning that all maximal independent sets have the same size, and suppose that every maximal clique has size ss. A graph is semi-perfect when its clique covering number θ(G)\theta(G) equals its independence number α(G) \alpha(G).

Zaare-Nahandi's conjecture. GG is semi-perfect.

Zaare-Nahandi proposed this conjecture as a characterization related to localizable graphs.

References

Status

  • Refuted: Ademir Hujdurović, Martin Milanič, and Bernard Ries. Graphs vertex-partitionable into strong cliques (arXiv, 2016) https://arxiv.org/abs/1609.06961

Source: Ademir Hujdurović, Martin Milanič and Bernard Ries, “Graphs vertex-partitionable into strong cliques”, arXiv:1609.06961 (2017).

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.