CONICET | Buscador de Institutos y Recursos Humanos

The clique-transversal number of a graph is the minimum size of a set of vertices meeting all the cliques. The clique-independence number is the maximum size of a collection of vertex-disjoint cliques. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation neither a characterization by forbidden induced subgraphs is known. Nevertheless, partial results in this direction have been obtained. For instance, a characterization of those line graphs that are clique-perfect is known in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect also by means of minimal forbidden induced subgraphs. This implies a O(n^2) time algorithm for deciding clique-perfectness of complements of line graphs.