کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647545 | 1342359 | 2013 | 10 صفحه PDF | دانلود رایگان |
On-line Ramsey theory studies a graph-building game between two players. The player called Builder builds edges one at a time, and the player called Painter paints each new edge red or blue after it is built. The graph constructed is the host graph. Builder wins the game if the host graph at some point contains a monochromatic copy of a given goal graph . In the SkSk-game variant of the typical game, the host graph is constrained to have maximum degree no greater than kk. The on-line degree Ramsey number R̊Δ(G) of a graph GG is the minimum kk such that Builder wins an SkSk-game in which GG is the goal graph. In this paper, we complete the investigation begun by Butterfield et al. into the on-line degree Ramsey numbers of nn-cycles. Namely, we show that R̊Δ(Cn)=4 for n≥3n≥3.
Journal: Discrete Mathematics - Volume 313, Issue 20, 28 October 2013, Pages 2084–2093