The incomparability-graph clique-separator conjecture
The incomparability-graph clique-separator conjecture
Let be fixed, let be a nonnegative integer, and let be an incomparability graph with no as a -shallow minor. Let be a clique cover of , and write for its number of cliques. A clique separator is a set of cliques whose removal separates into two subgraphs.
Clique-separator conjecture. There is a clique cover in such that removing
cliques from separates into two subgraphs, each of which can be covered by at most
cliques from .
Such a separator would provide a quantitative separation property for incomparability graphs excluding a fixed balanced complete bipartite graph as a shallow minor. The source presents this as a conjecture and gives no resolution, so it remains open.
Sources & referencesView supporting material
Primary source
Farhad Shahrokhi, “Largest reduced neighborhood clique cover number revisited”, arXiv:1705.02537 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.