Clique-Critical Graphs

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal completes) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We present a new characterization of clique-critical graphs, and show the only way of adding vertices to a graph without changing its clique graph. We prove that if G has m edges then any clique-critical graph in K−1(G) has at most 2m vertices. Finally, we demonstrate the NP-completeness of the clique-critical graph recognition problem.