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 the question of Zhu (2009) whether this difference, for all graphs, can be bounded by a common constant. By a classical correspondence, our result translates to the framework of on-line coloring of uniform hypergraphs. This way we obtain that for every on-line two coloring algorithm there exists a $k$-uniform hypergraph with $\Theta(2^k)$ edges on which the strategy fails. The results are derived through an analysis of a natural family of chip games.
@article{10_37236_5723,
author = {Lech Duraj and Grzegorz Gutowski and Jakub Kozik},
title = {Chip games and paintability},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/5723},
zbl = {1339.05129},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5723/}
}
TY - JOUR
AU - Lech Duraj
AU - Grzegorz Gutowski
AU - Jakub Kozik
TI - Chip games and paintability
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5723/
DO - 10.37236/5723
ID - 10_37236_5723
ER -
%0 Journal Article
%A Lech Duraj
%A Grzegorz Gutowski
%A Jakub Kozik
%T Chip games and paintability
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5723/
%R 10.37236/5723
%F 10_37236_5723
Lech Duraj; Grzegorz Gutowski; Jakub Kozik. Chip games and paintability. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5723
