We show that Erdős-Renyi random graph with constant density has correspondence chromatic number O(n/√(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. 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.
This video was produced by the Simons Institute, and forms part of the workshop Structural Results.
