The clique operator \(K\) maps a graph \(G\) into its clique graph, which is the intersection graph of the (maximal) cliques of \(G\). Recognizing clique graphs is a problem known to be in NP, but no polynomial time algorithm or proof of NP-completeness is known. In this note we prove that this recognition problem can be reduced to the case of graphs of diameter at most two.
Citation
Marisa Gutierrez, Joao Meidanis. On Clique Graph Recognition[J], Ars Combinatoria, Volume 063. 207-210. .