Coordinated graphs and clique graphs of clique-Helly perfect graphs

Abstract

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.