Chromatic characterization of biclique covers (Q2368922)

\(B \subseteq E\) is a biclique of a graph \(G=(V,E)\) if \(B\) is the edge-set of a complete bipartite subgraph of \(G\). For given \(G\) and \(k\), it is NP-complete to decide whether \(G\) has a biclique consisting of at least \(k\) edges, and whether all edges of \(G\) can be covered by at most \(k\) bicliques. This paper considers 0-1 linear programming formulations of these problems, and their continuous relaxations. The research was motivated by an open problem of \textit{P. C. Fishburn} and \textit{P. L. Hammer} [Discrete Math. 160, 127--148 (1996; Zbl 0861.05035)].