We will make use of the following key result in graph theory and communication complexity. We let \(\chi (G)\)  be the chromatic number of the simple graph \(G\) . We also set \(\mathrm {bp}(G)\)  be the biclique partition number of \(G\) , i.e., the minimum number of complete bipartite graphs needed to partition the edge set of \(G\) . The following result lies in the intersection of complexity theory and graph theory and is a result of numerous works [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}. Motivation was the Alon–Saks–Seymour problem in graph theory, which asks: How large
a gap can there be between the chromatic number of a graph and its biclique partition
number?
