On clique-perfect and K-perfect graphs
A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c-clique-perfect. A graph G is K-perfect when...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03817032_v80_n_p97_Bonomo |
| Aporte de: |
| Sumario: | A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c-clique-perfect. A graph G is K-perfect when its clique graph K(G) is perfect. In this work, relations are described among the classes of perfect, K-perfect, clique-perfect and c-clique-perfect graphs. Besides, partial characterizations of K-perfect graphs using polyhedral theory and clique subgraphs are formulated. |
|---|