Clique problem, cutting plane proofs and communication complexity

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, we consider the following communication game on a given graph G with maximum bipartite clique size K. Two parties separately receive disjoint subsets A, B   of vertices such that |A|+|B|>K|A|+|B|>K. The goal is to identify a nonedge between A and B  . We prove that O(logn) bits of communication are enough for any n-vertex graph.

► The find-a-nonedge game for individual graphs is considered.
► The game is related to the cutting plane complexity of Maximum Biclique problem.
► A surprising upper bound on its communication complexity is proved.