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-line Ramsey Theory for Bounded Degree Graphs. | On-line Ramsey Theory for Bounded Degree Graphs Jane Butterfield Tracy Grauman William B. Kinnersley Kevin G. Milans Christopher Stocker Douglas B. West University of Illinois Urbana IL . Submitted Nov 9 2010 Accepted Jun 15 2011 Published Jul 1 2011 Mathematics Subject Classification 05C55 05C57 Abstract When graph Ramsey theory is viewed as a game Painter 2-colors the edges of a graph presented by Builder . Builder wins if every coloring has a monochromatic copy of a fixed graph G. In the on-line version iteratively Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class H. Builder wins the game G H if a monochromatic copy of G can be forced. The on-line degree Ramsey number Ra G is the least k such that Builder wins G H when H is the class of graphs with maximum degree at most k. Our results include 1 ra G 3 if and only if G is a linear forest or each component lies inside K1 3. 2 ra G A G 1 1 where t maxuveE G min d u d v . 3 Ra G d1 d2 1 for a tree G where d1 and d2 are two largest vertex degrees. 4 4 RA Cn 5 with RA Cn 4 except for finitely many odd values of n. 5 Ra G 6 when A G 2. The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays consistently . 1 Introduction The classical problem of graph Ramsey theory specifies a target graph G and seeks a graph H such that every 2-coloring of E H produces a monochromatic copy of G. For such H we write H G and say that H arrows G. More generally when every s-coloring of E H produces a monochromatic G we write H A G. Ramsey s Theorem guarantees for every G that such a graph H exists. The Ramsey number R G s or R G when s 2 is the minimum number of vertices in such a graph H. Email addresses jbutter2@ grauman2@ wkinner2@ milans@ stocker2@ west@. Research of . .
