INVESTIGADORES
BONOMO flavia
artículos
Título:
Clique-perfectness of complements of line graphs
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; SAFE, MARTÍN DARÍO; WAGLER, ANNEGRET KATRIN
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2015 vol. 186 p. 19 - 44
ISSN:
0166-218X
Resumen:
A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and an $O(n^2)$-time algorithm to recognize such graphs. These results follow from a characterization and a linear-time recognition algorithm for matching-perfect graphs, which we introduce as graphs where the maximum number of pairwise edge-disjoint maximal matchings equals the minimum number of edges intersecting all maximal matchings for each subgraph. Thereby, we completely describe the linear and circular structure of the graphs containing no bipartite claw, from which we derive a structure theorem for all those graphs containing no bipartite claw that are Class~2 with respect to edge-coloring.