On strong biclique covering. (Q2846625)

A subgraph of a graph \(G\) which is a complete bipartite graph is termed a biclique. A biclique cover of \(G\) is a collection of bicliques covering the edges of \(G\). The biclique covering number of \(G\) is the minimum number of bicliques over all biclique covers of \(G\). A \(t\)-strong biclique cover of \(G\) is a biclique cover consisting of \(t\) sets \(H_1,\dots ,H_t\) where each \(H_i\) is a generalization of an induced matching: each \(H_i\) consists of disjoint bicliques such that there is no edge in \(G\) joining any two of them. The strong bliclique covering index \(S(G)\) is the minimum number \(t\) for which there exists a \(t\)-strong biclique cover of \(G\). An upper bound for the strong biclique covering index of a product of two graphs \(G\) and \(H\) (Cartesian product, categorical product, strong product, Cartesian sum, lexicographic product) is given in terms of \(S(G), S(H)\) and the chromatic numbers of \(G\) and \(H\). Similarly, an upper bound for the strong biclique covering index of the Mycielski graph of \(G\) is given.