Disproving the normal graph conjecture

Speaker(s)

Lucas Pastor

Date

Feb. 8, 2018, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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é.

---