Back to Search
Start Over
Clique-perfectness and balancedness of some graph classes.
- Source :
-
International Journal of Computer Mathematics . Oct2014, Vol. 91 Issue 10, p2118-2141. 24p. - Publication Year :
- 2014
-
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 ofP4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for anyP4-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. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00207160
- Volume :
- 91
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- International Journal of Computer Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 98624560
- Full Text :
- https://doi.org/10.1080/00207160.2014.881994