Disproving the normal graph conjecture

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 and Stéphan Thomassé.