Bounds on partial online list colouring

Assume G is an n-vertex graph with choice number ch(G)=s. Albertson, Grossman and Haas [6] conjectured that if t≤s is a positive integer, then for any t-list assignment L, G has an induced subgraph G′ such that G′ is L-colourable and |V(G′)|≥tsn. This paper studies the online version of this conjecture: if G has paint number χP(G)=s and each vertex is given t tokens for some integer t≤s, then Painter can colour at least tsn vertices. We prove that if s=tk+r, then Painter can colour at least (1−p)n vertices, where p is the root of the polynomial P(x)=x−(1−kx+1−kr)t in the interval [0,1]. The k=1 case of the result was proved in [5]. When k≥2, our result implies that Painter can colour at least 1213tsn vertices.