On clique graphs with linear size

Abstract

The clique graph H = K (G) of is the intersection graph of the collection of maximal cliques of G. In this case, G is a clique-inverse graph of H. By examining K (G), we describe some sufficient conditions for the number of maximal cliques of G to be bounded by O(|VG|). These conditions are then applied to analyze the complexity of recognizing clique-inverse graphs of various families of graphs.