Chip Games and Paintability

[摘要] We prove that the paint number of the complete bipartite graph $K_{N,N}$ is $\log N + O(1)$. As a consequence, we get that the difference between the paint number and the choice number of $K_{N,N}$ is $\Theta(\log \log N)$. This answers in the negative th

[学科分类] 离散数学和组合数学

[关键词] Paintability;List coloring;Property B;On-Line algorithms