Séminaire CORNET – Cléophée Robin – 05/06/2025
Nous avons le plaisir de vous inviter au séminaire de l’équipe CORNET, qui se tiendra le jeudi 5 juin à 11h35 en salle C057 (ancienne BU). À cette occasion, nous accueillerons Cléophée Robin, enseignante-chercheuse à l’IRIF, qui nous présentera ses travaux intitulés : _________________________________________________________ Clique-covering co-bridge-free prismatic graphs Résumé : 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 Plus d'infos
