INVESTIGADORES
SAFE Martin Dario
artículos
Título:
Clique-perfectness and balancedness of some graph classes
Autor/es:
FLAVIA BONOMO; GUILLERMO DURÁN; MARTÍN DARÍO SAFE; ANNEGRET KATRIN WAGLER
Revista:
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Editorial:
TAYLOR & FRANCIS LTD
Referencias:
Lugar: Londres; Año: 2014 vol. 91 p. 2118 - 2141
ISSN:
0020-7160
Resumen:
A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.