AbstractWe study here lifts and random lifts of graphs, as defined by Amit and Linial (Combinatorica 22 (2002), 1–18). We consider the Hadwiger number η and the Hajós number σ of ℓ‐lifts of Kn and analyze their extremal as well as their typical values (that is, for random lifts). When ℓ = 2, we show that ${n \over 2} \leq \eta \leq n$, and random lifts achieve the lower bound (as n → ∞). For bigger values of ℓ, we show $\Omega({n \over {\sqrt{\log n}}}) \leq \eta \leq n\sqrt{\ell}$. We do not know how tight these bounds are, and in fact, the most interesting question that remains open is whether it is possible for η to be o(n). When ℓ < O(log n), almost every ℓ‐lift of Kn satisfies η = Θ(n) and for $\Omega(\log{n}) \leq \ell \leq n^{{1 \over 3} - \varepsilon}$, almost surely $\eta = \Theta({n\sqrt{\ell} \over {\sqrt{\log{n}}}})$. For bigger values of ℓ, $\Omega({n\sqrt{\ell} \over {\sqrt{\log{\ell}}}}) \leq \eta \leq n\sqrt{\ell}$ almost always. The Hajós number satisfies $\Omega(\sqrt{n}) \leq \sigma \leq n$, and random lifts achieve the lower bound for bounded ℓ and approach the upper bound when ℓ grows. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006