Clique-perfectness and balancedness of some graph classes

Abstract

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 P₄-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P₄-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.

Keywords:

• balanced graphs
• clique-perfect graphs
• diamond-free graphs
• P₄-tidy graphs
• paw-free graphs
• recognition algorithms

2010 AMS Subject Classifications:

• 05C17
• 05C75
• 05C85

Acknowledgements

The authors are indebted to the referees for insightful comments, corrections, and suggestions that helped to improve this paper. The first three named authors were partially supported by UBACyT Grant 20020100100980, CONICET PIP 112-200901-00178, and ANPCyT PICT-2012-1324 (Argentina). G. Durán was also partially supported by FONDECyT Grant 1110797 and Millennium Science Institute ‘Complex Engineering Systems’ (Chile).