Clique-perfectness of complements of line graphsReport as inadecuate

Clique-perfectness of complements of line graphs - Download this document for free, or read online. Document in PDF available to download.


A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliquesequals the minimum number of vertices intersecting all maximal cliques for each inducedsubgraph. In this work, we give necessary and sufficient conditions for the complement ofa line graph to be clique-perfect and an On2-time algorithm to recognize such graphs.These results follow from a characterization and a linear-time recognition algorithm formatching-perfect graphs, which we introduce as graphs where the maximum number ofpairwise edge-disjoint maximal matchings equals the minimum number of edges intersectingall maximal matchings for each subgraph. Thereby, we completely describe the linearand circular structure of the graphs containing no bipartite claw, from which we derivea structure theorem for all those graphs containing no bipartite claw that are Class 2 withrespect to edge-coloring.Nota general

Artículo de publicación ISI

Author: Bonomo, Flavia; - Durán, Guillermo; - Safe, Martín D.; - Wagler, Annegret K.; -



Related documents