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.
- Choosability and paintability of the lexicographic product of graphs
- Characterization of \((2m,m)\)-paintable graphs
- Mr. Paint and Mrs. Correct
- Towards an on-line version of Ohba's conjecture
- Every planar graph is 1-defective \((9,2)\)-paintable
- The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
- Paint cost and the frugal distinguishing number
- On-line list coloring of matroids
- Critically paintable, choosable or colorable graphs
- Chip games and paintability
This page was built for publication: Mr. Paint and Mrs. Correct go fractional
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551235)
