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: On the path-avoidance vertex-coloring game. | On the path-avoidance vertex-coloring game Torsten Mtitze Reto Spỏheư Institute of Theoretical Computer Science Algorithms and Complexity Group ETH Zurich Max-Planck-Institut fur Informatik 8092 Zurich Switzerland 66123 Saarbrucken Germany muetzet@ rspoehel@ Submitted Mar 29 2011 Accepted Jul 21 2011 Published Aug 12 2011 Mathematics Subject Classifications 05C57 05C80 05D10 Abstract For any graph F and any integer r 2 the online vertex-Ramsey density of F and r denoted m F r is a parameter defined via a deterministic two-player Ramsey-type game Painter vs. Builder . This parameter was introduced in a recent paper arXiv where it was shown that the online vertex-Ramsey density determines the threshold of a similar probabilistic one-player game Painter vs. the binomial random graph Gnp . For a large class of graphs F including cliques cycles complete bipartite graphs hypercubes wheels and stars of arbitrary size a simple greedy strategy is optimal for Painter and closed formulas for m F r are known. In this work we show that for the case where F Pf is a long path the picture is very different. It is not hard to see that m m r 1 1 k Pj r for an appropriately defined integer k Pe r and that the greedy strategy gives a lower bound of k Pj r F. We construct and analyze Painter strategies that improve on this greedy lower bound by a factor polynomial in and we show that no superpolynomial improvement is possible. An extended abstract of this work will appear in the proceedings of EuroComb 11. The author was supported by a fellowship of the Swiss National Science Foundation. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P163 1 1 Introduction The online vertex-Ramsey density Consider the following deterministic two-player game The two players are called Builder and Painter and the board is a vertex-colored graph that grows in each step of the game. Painter wants to avoid creating a monochromatic copy of some fixed graph F and her .
