A biclique is a maximal set of vertices in a graph that induces a complete bipartite subgraph. The biclique graph of a graph G is the intersection graph of all bicliques of G and we denote such graph by KB( G ). In this work we introduce the concept of biclique parts of G and the inclusion graph of biclique parts of G, denoted by BP( G ). We show that the class of BP( K 3 –free) graphs is the same as a subclass of comparability graphs which we introduce as skew-IIC comparability graphs, from which we derive a characterization of KB( K 3 –free) graphs. We also present a proper subclass of K 3 –free graphs such that its class of biclique graphs is the same as the class of biclique graphs of all K 3 –free graphs. Furthermore, it is proved that the problem of computing a preimage of a KB m ( K 3 –free) graph can be reduced to a variation of the graph sandwich problem.

A biclique is a maximal set of vertices in a graph that induces a complete bipartite graph. The biclique graph KB(G) of a graph G is the intersection graph of all bicliques in G. In this work, we introduce the concept of differentiating edges and non-edges between pairs of intersecting bicliques in a graph and the corresponding variants of the biclique graph: the edge differentiated (KBedif) and the non-edge differentiated (KBndif) biclique graphs. Two bicliques are mutually included if they can be partitioned respectively into (X1, Y1) and (X2, Y2) such that X1 c X2 and Y2 c Y1. We show that all pairs of mutually included bicliques are non-edge differentiated, but they are not edge differentiated. We show that every pair of intersecting bicliques are differentiated by either edge or non-edge. Finally, we prove that graphs are free of edge differentiated bicliques if and only if they are (K3, C5)-free and that graphs are free of non-edge differentiated bicliques if and only if they are (P4, paw)-free.

A biclique of a graph G is a maximal complete bipartite induced subgraph of G with at least one edge. We define and study the time complexity of the problems of finding the minimum biclique transversal and maximum biclique independent set of a graph G, denoted by αb(G) and τb(G) respectively. We prove that the Biclique-Transversal and Biclique-Independent-Set problems are NP-Complete for the classes of split graphs, planar graphs C4-free with ∆ = 4, and bipartite C4-free graphs with ∆ = 4. In addition, we provide polinomial time algorithms for block graphs and split gem-free graphs. Finally, we introduce the concept of biclique-perfectness.

A biclique of a graph is a maximal complete bipartite subgraph. The biclique graph of a graph G, KB(G), defined as the intersection graph of the bicliques of G, was introduced and characterized in 2010 by Groshaus and Szwarcfiter. However, this characterization does not lead to polynomial time recognition algorithms, and the time complexity of its recognition problem remains open. There are some works on this problem when restricted to some classes. In this work we give a characterization of the biclique graph of a K3-free graph G. We prove that KB(G) is the square graph of a particular graph which we call Mutually Included Biclique Graph of G, KBm(G). Although it does not lead to a polynomial time recognition algorithm, it gives a new tool to prove properties of biclique graphs (restricted to K3-free graphs) using known properties of square graphs. For instance we generalize a property about induced P3's in biclique graphs to a property about stars and proved a conjecture posted by Groshaus and Montero, when restricted to K3-free graphs. Also we give another characterization of the class of biclique graphs of bipartite graphs. We prove that KB(bipartite) = (IIC-comparability)2, where IIC-comparability is a subclass of comparability graphs that we call Interval Intersection Closed Comparability.