Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Mr. Paint and Mrs. Correct go fractional. | Mr. Paint and Mrs. Correct go fractional Grzegorz Gutowski Theoretical Computer Science Department Jagiellonian University Kraków Poland grzegorz.gutowski@tcs.uj.edu.pl Submitted Mar 14 2011 Accepted Jun 22 2011 Published Jul 1 2011 Mathematics Subject Classifications 05C15 05C57 68W27 Abstract 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. 1 Introduction We start with a short introduction of the basic notions. Consider a finite and simple graph G V E . A list assignment L is a function assigning a set L v to each vertex v G V. We say that L is a-long if L v a for each vertex v G V. A function assigning a subset v c L v to each vertex v G V is an L b -colouring if the following conditions are met Vv G V v b V u w G E u n w 0. The graph G is a b -colourable if there exists an La b -colouring from a list assignment La in which La v 0 . a 1 for all v G V. If for any given a-long list assignment L there exists an L b -colouring then G is called a b -choosable. Following 1 we define the fractional chromatic number XF G and the choice ratio chF G Af G inf a G is a b -colourable THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P140 1 chF G inf b G is a b -choosable . Observe that the standard notions of chromatic number x G and choice number ch G can be equivalently restated as follows x G min a G is a 1 -colourable
