Geodesic
Mr. Paint and Mrs. Correct go fractional
The electronic journal of combinatorics, Tome 18 (2011) no. 1

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
We study a fractional counterpart of the on-line list colouring game "Mr. Paint and Mrs. Correct" introduced recently by Schauz. 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 the paper of Alon et al. 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.
DOI : 10.37236/627
Classification : 05C15, 05C57, 68W27
Mots-clés : on-line list colouring game 
Grzegorz Gutowski. Mr. Paint and Mrs. Correct go fractional. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/627
@article{10_37236_627,
     author = {Grzegorz Gutowski},
     title = {Mr. {Paint} and {Mrs.} {Correct} go fractional},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/627},
     zbl = {1222.05058},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/627/}
}
TY  - JOUR
AU  - Grzegorz Gutowski
TI  - Mr. Paint and Mrs. Correct go fractional
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/627/
DO  - 10.37236/627
ID  - 10_37236_627
ER  - 
%0 Journal Article
%A Grzegorz Gutowski
%T Mr. Paint and Mrs. Correct go fractional
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/627/
%R 10.37236/627
%F 10_37236_627

Cité par Sources :