The incomparability-graph clique-separator conjecture

Let pp be fixed, let tt be a nonnegative integer, and let GG be an incomparability graph with no Kp,pK_{p,p} as a tt-shallow minor. Let CC be a clique cover of GG, and write C|C| for its number of cliques. A clique separator is a set of cliques whose removal separates GG into two subgraphs.

Clique-separator conjecture. There is a clique cover CC in GG such that removing

O(C)O\left(\sqrt{|C|}\right)

cliques from CC separates GG into two subgraphs, each of which can be covered by at most

2C3\frac{2|C|}{3}

cliques from CC.

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

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.