Le problème de coloration est un sujet bien étudié et sa complexité est connue pour plusieurs classes de graphes. Cependant, la question de sa complexité reste ouverte pour la classe des graphes antiprismatiques, qui sont le complément des graphes prismatiques et l'un des quatre cas restants mis en évidence par Lozin et Malishev. Dans cet exposé, nous nous concentrons sur la question équivalente de la complexité du problème de couverture des cliques dans les graphes prismatiques. 

Un graphe G est prismatique si, pour chaque triangle T de G, chaque sommet de G n'appartenant pas à T a un voisin unique dans T. Un graphe est sans co-bridge s'il ne contient pas de sous-graphe induit C_4+2K_1. Nous proposons un algorithme en temps polynomial qui résout le problème de couverture de cliques dans les graphes prismatiques sans co-bridge. Il s'appuie sur la description structurelle donnée par Chudnovsky et Seymour, ainsi que sur les travaux ultérieurs de Preissmann, Robin et Trotignon.

Nous montrons que les graphes prismatiques sans co-bridge ont un nombre limité de triangles disjoints, ce qui implique que l'algorithme présenté par Preissmann et al. s'applique.