科研之友
微信
新浪微博
Facebook
分享链接
摘要
Consider the following one-person game: let S = {F-1, F-2, ... , F-r} be a family of forbidden graphs. The edges of a complete graph are randomly shown to the Painter one by one, and he must color each edge with one of r colors when it is presented, without creating some fixed monochromatic forbidden graph F-i in the i-th color. The case of all graphs F-i being cycles is studied in this paper. We give a lower bound on the threshold function for online S-avoidance game, which generalizes the results of Marciniszyn, Spohel and Steger for the symmetric case. [Combinatorics, Probability and Computing, Vol. 18, 2009: 271-300.]
- 出版日期2015-4
- 单位北京交通大学
