Speaker: Xuding Zhu

Title: Online list colouring of graphs

Abstract: List colouring of graphs is a model for some resource distribution problems. Sometimes decisions are made based on partial information. In such cases, online list colouring of graphs maybe an appropriate model. Online list colouring of a graph $G$ is defined through a game played by two players: Lister and Painter.  At the beginning of the game, each vertex $v$ is given a number $f(v)$ of tokens, which is the number of colours available to $v$. In each round, Lister chooses a set $M$ of uncoloured vertices, and removes one token from each chosen vertex. Painter chooses an independent subset $X$ of $M$, and colours vertices in $X$. If at the end of some round, an uncoloured vertex has no more tokens left, then Lister wins the game. Otherwise, at the end of some round, all vertices are coloured, Painter wins the game. We say $G$ is online $k$-choosable, if Painter has a winning strategy for the game provided that  each vertex initially has $k$ tokens. Online list colouring of graphs has attracted some recent attention. In this talk, I shall survey results, methods and problems in this area.