Zaare-Nahandi's semi-perfectness conjecture for multipartite well-covered graphs
Zaare-Nahandi's semi-perfectness conjecture for multipartite well-covered graphs
Let be an -partite well-covered graph, meaning that all maximal independent sets have the same size, and suppose that every maximal clique has size . A graph is semi-perfect when its clique covering number equals its independence number .
Zaare-Nahandi's conjecture. is semi-perfect.
Zaare-Nahandi proposed this conjecture as a characterization related to localizable graphs. It is refuted: the paper constructs counterexamples, using a reduction from -colorability in triangle-free 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
Ademir Hujdurović, Martin Milanič and Bernard Ries, “Graphs vertex-partitionable into strong cliques”, arXiv:1609.06961 (2017).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.