On clique graphs with linear size

Submitted by Elaine Almeida (elaine.almeida@nce.ufrj.br) on 2017-08-15T13:36:04Z No. of bitstreams: 1 07_99_000611268.pdf: 215680 bytes, checksum: 6e1d71e341e352c388e397bc4edfcc40 (MD5)Made available in DSpace on 2017-08-15T13:36:04Z (GMT). No. of bitstreams: 1 07_99_000611268.pdf: 215680 bytes, checksum: 6e1d71e341e352c388e397bc4edfcc40 (MD5) Previous issue date: 1999-12-31The 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