Sophie Spirkl

The Erdos-Hajnal conjecture states that for every graph H there exists c > 0 such that every n-vertex graph G either contains H as an induced subgraph, or has a clique or stable set of size at least n^c. I will talk about a proof of this conjecture...

Abstract: A k-list-assignment for a graph G is a function L from V(G) to the set of subsets of {1,…,k}. The list-k-colouring problem asks, given G and a k-list-assignment L, is there a colouring f of G with f(v) in L(v) for all v in V(G)? This...

The Erdos-Hajnal conjecture states that for every graph H there exists $c > 0$ such that every n-vertex graph $G$ either contains $H$ as an induced subgraph, or has a clique or stable set of size at least $n^c$. I will talk about a proof of this...