Abstract
We show that Erdős-Renyi random graph with constant density has correspondence chromatic number O(n/\sqrt{logn}); this matches a prediction from linear Hadwiger’s conjecture for correspondence colouring. The proof follows from a sufficient condition for correspondence colourability in terms of the numbers of independent sets. We conjecture the truth to be of order O(n/logn) as suggested by the random correspondence assignment. This is joint work with Zdenek Dvorak.