Cléophée Robin - Clique-covering co-bridge-free prismatic graphs

2 mars 26

Speaker: Cléophée Robin

Title: Clique-covering co-bridge-free prismatic graphs

Room: A711

Date: 02/03/2026

Abstract:

A graph G is prismatic if for every triangle T of G, every vertex of G that is not in T, has exactly one neighbor in T. The complement of a prismatic graph is called antiprismatic. The complexity of the coloring problem when restricted to prismatic graphs is unknown. Hence, the complexity of the clique-covering problem on prismatic graphs is also unknown. 

Chudnovsky and Seymour gave a full structural description of prismatic graphs. They divided the class in two subclasses : the orientable prismatic graphs and the non-orientable prismatic graphs.  Preissman, Robin and Trotignon gave an algorithm to solve the clique problem in non-orientable prismatic graphs in polynomial time.

We show this algorithm can also be used for prismatic graphs with no 2K_1 + C_4 (co-bridge), whether they are orientable or not. To achieve this, we show that this class of graphs admits a bounded number of disjoint triangles through a cautious analysis of their structure.