At round Lister choose a set V of uncoloured vertices. removes one token from each vertex of V is the set of vertices which has colour i as a permiSSible colour Painter chooses an independent subset 1; of V vertices in I, are coloured by colour i
At round i is the set of vertices which has colour i as a permissible colour. Vi Painter chooses an independent subset Ii of Vi vertices in Ii are coloured by colour i. Lister choose a set of uncoloured vertices, removes one token from each vertex of Vi Vi
If at the end of some round there is an uncolored vertex with no tokens left. then Lister wins If all vertices are coloured then Painter wins the game
If at the end of some round, there is an uncolored vertex with no tokens left, then Lister wins. If all vertices are coloured then Painter wins the game
G is f-paintable if Painter has a winning strategy for the f-painting game G is k-paintablel if G is f-paintable for f(x)=k for every x Thelpaint number ch(G) of g is the minimum k for which G is k-paintable
G is f-paintable if Painter has a winning strategy for the f-painting game. G is k-paintable if G is f-paintable for f(x)=k for every x. The paint number of G is the minimum k for which G is k-paintable. ch ( ) p G
On-line list colouring Painter start colouring the graph before having the full information of the list choice number ch(G)=mink: G is k-choosable ch(G)≥ch(G)
choice number ch(G) = min k :Gis k -choosable chp (G ) ch(G ) Painter start colouring the graph after having the full information of the list OnList colouring: -line list colouring: before
2.2.4 is not 2-paintable 2.2.4 Theorem [Erdos-Rubin- Taylor (1979) 6, 2. 2.2n IS 2-choosable
2,2,4 Theorem [Erdos-Rubin-Taylor (1979)] 2,2,2n is 2-choosable. 2,2,4 is not 2-paintable