Contents

Ars Combinatoria

  • Research article

On Clique-Perfect and \(K\)-Perfect Graphs

Flavia Bonomo1, Guillermo Duran2, Marina Groshaus3, Jayme L Szwarcfiter4
1Dep. de Computacién, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Atres, Argentina.
2Dep. de Ingenieria Industrial, Facultad de Ciencias Fisicas y Matemdticas, Universidad de Chile, Santiago, Chile.
3Dep, de Computacién, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina.
4 Institulo de Matemdtica, NCE and COPPE, Universidade Federal do Rio de Janeiro, Caira Postal 2324, 20001-970 Rio de Janeiro, RJ, Brasil.
  • Published: 31/07/2006

Abstract

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.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Flavia Bonomo, Guillermo Duran, Marina Groshaus, Jayme L Szwarcfiter. On Clique-Perfect and \(K\)-Perfect Graphs[J], Ars Combinatoria, Volume 080. 97-112. .