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 the normal view instead:

scientific article; zbMATH DE number 5923996
Language Label Description Also known as
default for all languages
No label defined
    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
      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

      Identifiers