Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

Flavia Bonomo, Maria Chudnovsky, Guillermo Durán

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc (HCA) graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect HCA graphs.

Original languageEnglish (US)
Pages (from-to)3485-3499
Number of pages15
JournalDiscrete Mathematics
Volume309
Issue number11
DOIs
StatePublished - Jun 6 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Clique-perfect graphs
  • Diamond-free graphs
  • Helly circular-arc graphs
  • K-perfect graphs
  • Perfect graphs

Fingerprint Dive into the research topics of 'Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs'. Together they form a unique fingerprint.

  • Cite this