Two well-known NP-complete problems for bipartite graphs are considered: biclique cover and biclique partition problems. These problems have applications in many fields of computer science, e.g., optimization of OLED displays, automata theory, computer security and role minimization in role-based access control systems. Moreover, a biclique cover number and a biclique partition number have direct connections to Boolean and binary ranks of binary matrices.
In this talk, I will show the upper bound on the biclique partition number in terms of the biclique cover number. I will also present results on the complexity of the biclique cover and the biclique partition problems for special graph classes. Finally, the results about binary rank of Kronecker product and the connected open question will be discussed.