Chip games and paintability

Lech Duraj, Grzegorz Gutowski, Jakub Kozik

We prove that the difference between the paint number and the choice number of a complete bipartite graph $K_{N,N}$ is $\Theta (\log \log N)$. That answers the question of Zhu (2009) wh…