The Clique Operator on Cographs and Serial Graphs

The {\bf clique graph} of a graph $G$ is the intersection graph $K(G)$ of the (maximal) cliques of $G$. The iterated clique graphs $K^{n}(G)$ are defined by $K^{0}(G)=G$ and $K^{i}(G)=K(K^{i-1}(G))$, where $i>0$ and $K$ is the clique operator. A {\bf cograph} is a graph with no induced subgraph isomorphic to $P_{4}$. In this article we describe the $K$-behaviour of cographs and give some partial results for the larger class of serial (i.e.~complement-disconnected) graphs.

2001