Mr. Paint and Mrs. Correct go fractional (Q551235)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Mr. Paint and Mrs. Correct go fractional |
scientific article; zbMATH DE number 5923996
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Mr. Paint and Mrs. Correct go fractional |
scientific article; zbMATH DE number 5923996 |
Statements
Mr. Paint and Mrs. Correct go fractional (English)
0 references
15 July 2011
0 references
Summary: We study a fractional counterpart of the on-line list colouring game ``Mr. Paint and Mrs. Correct'' introduced recently by Schauz [\textit{U. Schauz}, ``Mr. Paint and Mrs. Correct,'' Electron. J. Comb. 16, No. 1, Research Paper R77, 18 p. (2009; Zbl 1186.05085)]. We answer positively a question of Zhu by proving that for any given graph the on-line choice ratio and the (off-line) choice ratio coincide. On the other hand it is known from a paper of \textit{N. Alon, Z. Tuza} and \textit{M. Voigt} [``Choosability and fractional chromatic numbers,'' Discrete Math. 165--166, 31--38 (1997; Zbl 0877.05020)] that the choice ratio equals the fractional chromatic number. It was also shown that the limits used in the definitions of these last two notions can be realised. We show that this is not the case for the on-line choice ratio. Both our results are obtained by exploring the strong links between the on-line choice ratio, and a new on-line game with probabilistic flavour which we introduce.
0 references
on-line list colouring game
0 references
0 references
0 references