Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

Flavia Bonomo, Maria Chudnovsky, Guillermo Durán

Research output: Contribution to journalArticle

19 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. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers 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. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.

Original languageEnglish (US)
Pages (from-to)1058-1082
Number of pages25
JournalDiscrete Applied Mathematics
Volume156
Issue number7
DOIs
StatePublished - Apr 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Claw-free graphs
  • Clique-perfect graphs
  • Hereditary clique-Helly graphs
  • Line graphs
  • Perfect graphs

Fingerprint Dive into the research topics of 'Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs'. Together they form a unique fingerprint.

  • Cite this