Clique-perfectness of complements of line graphs
Clique-perfectness-of-complements-of-line-graphs.pdf (655.7Kb)Abstract
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(n2)-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.
General note
Artículo de publicación ISI
Patrocinador
The authors would like to thank an anonymous referee for suggestions and corrections that improved the presentation of
this paper. First, second and third authors were partially supported by UBACyT Grant 20020100100980, CONICET PIP 112-
200901-00178, and ANPCyT PICT-2012-1324 (Argentina). The second author was partially supported by FONDECyT Grant
1140787 and Complex Engineering Systems Institute (ISCI, Chile).
Identifier
URI: https://repositorio.uchile.cl/handle/2250/132908
DOI: DOI: 10.1016/j.dam.2015.01.012
Quote Item
Discrete Applied Mathematics 186 (2015) 19–44
Collections
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile