Chip games and paintability (Q726662)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chip games and paintability |
scientific article |
Statements
Chip games and paintability (English)
0 references
13 July 2016
0 references
Summary: 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 \textit{X. Zhu} [Electron. J. Comb. 16, No. 1, Research Paper R127, 16 p. (2009; Zbl 1186.05061)] 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.
0 references
paintability
0 references
list coloring
0 references
property B
0 references
online algorithms
0 references