Almost every graph is divergent under the biclique operator

A biclique of a graph GG is a maximal induced complete bipartite subgraph of GG. The biclique graph of GG denoted by KB(G)KB(G), is the intersection graph of all the bicliques of GG. The biclique graph can be thought as an operator between the class of all graphs. The iterated biclique graph of GG denoted by KBk(G)KBk(G), is the graph obtained by applying the biclique operator kk successive times to GG. The associated problem is deciding whether an input graph converges, diverges or is periodic under the biclique operator when kk grows to infinity. All possible behaviors were characterized recently and an O(n4)O(n4) algorithm for deciding the behavior of any graph under the biclique operator was also given. In this work we prove new structural results of biclique graphs. In particular, we prove that every false-twin-free graph with at least 13 vertices is divergent. These results lead to a linear time algorithm to solve the same problem.