|
|||||
|
|
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
|
| Authors: | Flavia Bonomo Maria Chudnovsky Guillermo Durán |
| Institution: | a Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina b Department of IEOR, Columbia University, New York, NY, USA c Department of Mathematics, Columbia University, New York, NY, USA d Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile |
| 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. |
| Keywords: | Claw-free graphs Clique-perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |