mardi 26 mars 2024

Vincent Limouzy, enseignant-chercheur au LIMOS, donnera un séminaire le 26 mars 2024 à 14h à INRIA dans la salle E006 du bâtiment Euler.

Son exposé intitulé « Recent results on CPT graphs »

Abstract :

A containment path in a tree graph (CPT) is a graph obtained by looking at a given collections of a path in a given tree. Each path represents a vertex. And two vertices u and v are adjacent, if the path Pv that represents vertex v is contained in the path Pu or the converse. This class of graph is a subclass of a well known class of comparability graphs. Unlike, many sub-classes of comparability graphs, the class of CPT graph is not a comparability invariant (in the sense that not all the transitive orientation yield a CPT representation). From that observation, Alcon, Guttirez and Gudino introduced two natural sub-classes: Dual CPT graph for which if a transitive orientation is representable, its dual (the orientation obtained by reversing the arcs) also admits a CPT representation. And Strongly CPT, where all the transitive representation admits a CPT model. From the definition, it is easy to notice that Strongly CPT graphs forms a subclass of Dually CPT graphs. They left as an open question whether the inclusion is strict or not. In this presentation we will show that actually both class coincide. To obtain this result we will rely on modular decomposition theory.