The clique operator K maps a graph G into its cliqeu graph, which is the intersection graph of thecliques of G. Among all the better studied graph operators, K seems to be the richest one and many questions regarding it remain open. IN particular, it is not known whether recognizign a clique graph is in P. In this note we describe our progress toward aswerign this question. We obtain a necessary condition for a graph to be in the image of K in terms of the presence of certain subgraphs A and B. We show that being a clique graph is not a property that is maintained by addition of twins. We present a result involving distances that reduces the recognition problem to graphs of idameter at most two. We also give a constructive characterization of K sup -1 for a fixed but generic G.
展开▼
