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: Trees with an On-Line Degree Ramsey Number of Four. | Trees with an On-Line Degree Ramsey Number of Four David Rolnick Massachusetts Institute of Technology Cambridge MA USA drolnick@ Submitted Dec 17 2010 Accepted Aug 11 2011 Published Sep 2 2011 Mathematics Subject Classification 05C55 05C57 05C05 Abstract 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 called the background graph. Builder s goal is to cause the background graph to contain a monochromatic copy of a given goal graph and Painter s goal is to prevent this. In the Sk-game variant of the typical game the background graph is constrained to have maximum degree no greater than k. The on-line degree Ramsey number Ra G of a graph G is the minimum k such that Builder wins an Sk-game in which G is the goal graph. Butterfield et al. previously determined all graphs G satisfying Ra G 3. We provide a complete classification of trees T satisfying Ra T 4. 1 Introduction The quintessential problem of Ramsey theory involves finding a monochromatic copy of a graph G within a larger graph whose edges are colored with some s colors. Given G and s we say that a graph H arrows G if every s-coloring of H contains a monochromatic G as a subgraph. Two basic parameters of Ramsey theory are The Ramsey number R G is the minimum number of vertices among graphs H that arrow G. The size Ramsey number R G is the minimum number of edges among graphs that arrow G. The numbers called on-line Ramsey numbers are based upon the following game which we consider in the 2-color case though an s-color generalization is possible Two THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P173 1 players called Builder and Painter generate a 2-colored graph H. Builder builds edges one at a time using some combination of existing vertices and new vertices. As each edge is built Painter paints it either red or blue.
