2 ALAN FRIEZE,DIETER MITSCHE,XAVIER PEREZ-GIMENEZ,AND PAWEL PRALAT All asymptotics throughout are as n-oo (we emphasize that the notations o()and O()refer to functions of n,not necessarily positive,whose growth is bounded;whereas e()and (.)always refer to positive functions).We say that an event in a probability space holds asymptotically almost surely (or a.a.s.)if the probability that it holds tends to 1 as n goes to infinity.We often write (n,p)when we mean a graph drawn from the distribution (n,p).Finally,for simplicity, we will write f(n)~g(n)if f(n)/g(n)1 as noo (that is,when f(n)=(1+0(1))g(n)) Now,we will briefly mention the relation to other known graph parameters.A proper colouring of a graph is a labelling of its vertices with colours such that no two adjacent vertices have the same colour.A colouring using at most k colours is called a (proper)k-colouring.The smallest number of colours needed to colour a graph G is called its chromatic number,and it is denoted by x(G).Let Lk be an arbitrary function that assigns to each vertex of G a list of k colours. We say that G is Lk-list-colourable if there exists a proper colouring of the vertices such that every vertex is coloured with a colour from its own list.A graph is k-choosable,if for every such function Lk,G is L-list-colourable.The minimum k for which a graph is k-choosable is called the list chromatic number,or the choice number,and denoted by xL(G).Since the choices for Lk contain the special case where each vertex is assigned the list of colours f1,2,...,k,it is clear that a k-choosable graph has also a k-colouring,and so x(G)<XL(G).It is also known that if a graph is k-paintable,then it is also k-choosable [13],that is,xL(G)<XP(G).Indeed, if there exists a function Lk so that G is not L-list-colourable,then Mr.Paint can easily win by fixing some permutation of all colours present in Lk and presenting at the i-th step all vertices containing the i-th colour of the permutation on their lists (unless the vertex was already removed before).Finally,it was shown in [16]that the paintability of a graph G on n vertices is at most x(G)logn+1.(All logarithms in this paper are natural logarithms.)Combining all inequalities we get the following: (1) X(G)≤Xz(G)≤XP(G≤x(G)logn+1. It follows from the well-known results of Bollobas [4],Luczak [11](see also McDiarmid [12])that the chromatic number of(n,p)a.a.s.satisfies (2) x(4(np)) log(1/(1-p))n 2log(np) for npoo and p bounded away from 1.The study of the choice number of (n,p)was initiated in [1],where Alon proved that a.a.s.,the choice number of (n,1/2)is o(n).Kahn then showed (see [2])that a.a.s.the choice number of(n,1/2)equals (1+o(1))(n1/2).In [7],Krivelevich showed that this holds for pn1/4,and Krivelevich,Sudakov,Vu,and Wormald 8]improved this to pn/3.On the other hand,Alon,Krivelevich,Sudakov [3]and Vu [15]showed that for any value of p satisfying 2<np n/2,the choice number is e(np/log(np)).Later,Krivelevich and Vu [10]generalized this to hypergraphs;they also improved the leading constants and showed that the choice number for C<np 0.9n (where C is a sufficiently large constant)is at most a multiplicative factor of 2+o(1)away from the chromatic number,the best known factor for p<n-1/3.Our results below (see Theorem 1,Theorem 2,and Theorem 3)show that even for the on-line case,for a wide range of p,we can asymptotically match the best known constants of the off-line case.Moreover,if np logn (for some function w=w(n)tending to infinity as noo), then we get the same multiplicative factor of 2+o(1). Our main results are the following theorems.The first one deals with dense random graphs. Theorem 1.Let e>0 be any constant,and suppose that (log log n)/3(log n)2n-1/3<p<1-e.2 ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ All asymptotics throughout are as n → ∞ (we emphasize that the notations o(·) and O(·) refer to functions of n, not necessarily positive, whose growth is bounded; whereas Θ(·) and Ω(·) always refer to positive functions). We say that an event in a probability space holds asymptotically almost surely (or a.a.s.) if the probability that it holds tends to 1 as n goes to infinity. We often write G (n, p) when we mean a graph drawn from the distribution G (n, p). Finally, for simplicity, we will write f(n) ∼ g(n) if f(n)/g(n) → 1 as n → ∞ (that is, when f(n) = (1 + o(1))g(n)). Now, we will briefly mention the relation to other known graph parameters. A proper colouring of a graph is a labelling of its vertices with colours such that no two adjacent vertices have the same colour. A colouring using at most k colours is called a (proper) k-colouring. The smallest number of colours needed to colour a graph G is called its chromatic number, and it is denoted by χ(G). Let Lk be an arbitrary function that assigns to each vertex of G a list of k colours. We say that G is Lk-list-colourable if there exists a proper colouring of the vertices such that every vertex is coloured with a colour from its own list. A graph is k-choosable, if for every such function Lk, G is Lk-list-colourable. The minimum k for which a graph is k-choosable is called the list chromatic number, or the choice number, and denoted by χL(G). Since the choices for Lk contain the special case where each vertex is assigned the list of colours {1, 2, . . . , k}, it is clear that a k-choosable graph has also a k-colouring, and so χ(G) ≤ χL(G). It is also known that if a graph is k-paintable, then it is also k-choosable [13], that is, χL(G) ≤ χP (G). Indeed, if there exists a function Lk so that G is not Lk-list-colourable, then Mr. Paint can easily win by fixing some permutation of all colours present in Lk and presenting at the i-th step all vertices containing the i-th colour of the permutation on their lists (unless the vertex was already removed before). Finally, it was shown in [16] that the paintability of a graph G on n vertices is at most χ(G) log n + 1. (All logarithms in this paper are natural logarithms.) Combining all inequalities we get the following: (1) χ(G) ≤ χL(G) ≤ χP (G) ≤ χ(G) log n + 1. It follows from the well-known results of Bollob´as [4], Luczak [11] (see also McDiarmid [12]) that the chromatic number of G (n, p) a.a.s. satisfies (2) χ(G (n, p)) ∼ log(1/(1 − p))n 2 log(np) , for np → ∞ and p bounded away from 1. The study of the choice number of G (n, p) was initiated in [1], where Alon proved that a.a.s., the choice number of G (n, 1/2) is o(n). Kahn then showed (see [2]) that a.a.s. the choice number of G (n, 1/2) equals (1 + o(1))χG (n,1/2). In [7], Krivelevich showed that this holds for p ≫ n −1/4 , and Krivelevich, Sudakov, Vu, and Wormald [8] improved this to p ≫ n −1/3 . On the other hand, Alon, Krivelevich, Sudakov [3] and Vu [15] showed that for any value of p satisfying 2 < np ≤ n/2, the choice number is Θ(np/ log(np)). Later, Krivelevich and Vu [10] generalized this to hypergraphs; they also improved the leading constants and showed that the choice number for C ≤ np ≤ 0.9n (where C is a sufficiently large constant) is at most a multiplicative factor of 2 + o(1) away from the chromatic number, the best known factor for p ≤ n −1/3 . Our results below (see Theorem 1, Theorem 2, and Theorem 3) show that even for the on-line case, for a wide range of p, we can asymptotically match the best known constants of the off-line case. Moreover, if np ≥ logω n (for some function ω = ω(n) tending to infinity as n → ∞), then we get the same multiplicative factor of 2 + o(1). Our main results are the following theorems. The first one deals with dense random graphs. Theorem 1. Let ε > 0 be any constant, and suppose that (log log n) 1/3 (log n) 2n −1/3 ≪ p ≤ 1 − ε