Georgia Institute of Technology College of Sciences

We show that Erdős-Renyi random graph with constant density has correspondence chromatic number $O(n/\sqrt{\log n})$; 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, following Bernshteyn's method. We conjecture the truth to be of order $O(n/\log n)$ as suggested by the random correspondence assignment. This is joint work with Zdenek Dvorak.