INVESTIGADORES
BONOMO Flavia
congresos y reuniones científicas
Título:
Clique-perfectness of complements of line graphs
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; SAFE, MARTÍN DARÍO; WAGLER, ANNEGRET KATRIN
Lugar:
Bariloche
Reunión:
Simposio; Latin-American Graphs and Optimization Symposium (LAGOS); 2011
Institución organizadora:
UBA, UNGS (Argentina) y Univ. Paris 13 (Francia)
Resumen:
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.