Mr. Paint and Mrs. Correct go fractional (Q551235)

From MaRDI portal





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
    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