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.