The chromatic number of random lifts of K5\e

Amit, Linial, and Matoušek (Random lifts of graphs III: independence and chromatic number, Random Struct. Algorithms, 2002) have raised the following question: Is the chromatic number of random h-lifts of K5 asymptotically (for h→∞) almost surely (a.a.s.) equal to a single number? In this paper, we offer the following partial result: The chromatic number of a random lift of K5\e is a.a.s. three. We actually prove a stronger statement where K5\e can be replaced by a graph obtained from joining a cycle to a stable set.