Séminaire


Date : 12 octobre 2016 14:00 - Salle :Salle du conseil

Disproving the normal graph conjecture


Lucas Pastor - G-SCOP , Grenoble

Possibilité de visio-conférence A graph G is said to be normal if there exists two coverings, C and S of its vertex set such that, every member of C induces a clique, every member of S induces a stable set, and every clique of C intersects every stable set of S. De Simone and Körner conjectured in 1999 that a graph G is normal if G does not contain C_5, C_7 and the complement of C_7 as an induced subgraph. By using probabilistic methods we disprove this conjecture. This is joint-work with Ararat Harutyunyan (University of Toulouse III) and Stéphan Thomassé (ENS Lyon).