The chromatic number of random lifts of complete graphs

JD Nir, Xavier Pérez Giménez

An $n$-lift of a graph $G$ is a graph from which there is an $n$-to-$1$ covering map onto $G$. Amit, Linial, and Matou\v sek (2002) raised the question of whether the chromatic num…