Coordinated graphs and clique graphs of clique-Helly perfect graphs

BONOMO, FLAVIA; DURÁN, GUILLERMO; GROSHAUS, MARINA

Utilitas Mathematica

Utilitas Mathematica Pub. Co.

Lugar: Winnipeg; Año: 2007 vol. 72 p. 175 - 191

0315-3681

A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of a minimum partition of the cliques of H into clique-independent sets, for every induced subgraph H of G. A graph G is K-perfect when its clique graph K(G) is perfect. The concept of special clique subgraph is defined, which leads us to the notion of c-coordinated graphs (coordination relative to these clique subgraphs). We prove that coordinated graphs are a subclass of perfect graphs and relate K-perfect graphs with c-coordinated graphs. Finally, clique graphs of clique-Helly and hereditary clique-Helly perfect graphs are analyzed.