Clique-Inverse Graphs of Bipartite Graphs

Abstract

The clique graph $K(G)$ of a given graph $G$ is the intersection graph of the collection of maximal cliques of $G$. Given a family $\mathcal{F}$ of graphs, the $clique-inversegraphs$ of $\mathcal{F}$ are the graphs whose clique graphs belong to $\mathcal{F}$. In this work, we describe characterizations for clique-inverse graphs of bipartite graphs, chordal bipartite graphs, and trees. The characterizations lead to polynomial time algorithms for the corresponding recognition problems.