Résumé: We consider the NP:complete problem of coloring the vertices of a graph so that no maximal clique of size at least two is monocolored. A basic property of graph colorations is that a coloration of a graph is also a good coloration of all subgraphs. This property allows to define various notions of ‘critical graphs’. Nothing like these is true for clique:colorations: first of all, a clique:coloration of G is usually not a clique:coloration of the subgraphs. In this note, we propose some alternative definitions of critical:graph for clique:coloration and we give some properties and families of critical:graphs.

Langue: Anglais