Huang–Sudakov's biclique partition–chromatic number conjecture
Statement
Let be a graph. Its biclique partition number is the minimum number of bicliques, that is, complete bipartite graphs, needed to partition the edge set of . Its chromatic number is the minimum number of stable sets in a partition of the vertex set of .
Huang–Sudakov's conjecture. For each integer , there exists a graph with biclique partition number and chromatic number at least
for some constant .
If true, this graph-theoretical statement would improve the known lower bound on the nondeterministic communication complexity of the clique-versus-stable-set problem from to . The exact deterministic and nondeterministic communication complexities remain unknown.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.