INVESTIGADORES
BONOMO Flavia
congresos y reuniones científicas
Título:
Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; SOULIGNAC, FRANCISCO JUAN; SUEIRO, GABRIEL
Lugar:
Puerto Varas
Reunión:
Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2007
Institución organizadora:
Universidad de Chile
Resumen:
A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph $G$ is coordinated if the chromatic number of the clique graph of $H$ equals the maximum number of cliques of $H$ with a common vertex, for every induced subgraph $H$ of $G$. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem,$W_4$,bull}-free, two superclasses of triangle-free graphs.