Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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í toán học quốc tế đề tài:Anti-Ramsey numbers for graphs with independent cycles Zemin Jin. | Anti-Ramsey numbers for graphs with independent cycles Zemin Jin Department of Mathematics Zhejiang Normal University Jinhua 321004 P.R. China zeminj in@hotmail.com Xueliang Li Center for Combinatorics and LPMC-TJKLC Nankai University Tianjin 300071 P.R. China lxl@nankai.edu.cn Submitted Dec 22 2008 Accepted Jul 2 2009 Published Jul 9 2009 Mathematics Subject Classifications 05C15 05C38 05C55 Abstract An edge-colored graph is called rainbow if all the colors on its edges are distinct. Let G be a family of graphs. The anti-Ramsey number AR n G for G introduced by Erdos et al. is the maximum number of colors in an edge coloring of Kn that has no rainbow copy of any graph in G. In this paper we determine the antiRamsey number AR n Q2 where Q2 denotes the family of graphs that contain two independent cycles. 1 Introduction An edge-colored graph is called rainbow if any of its two edges have distinct colors. Let G be a family of graphs. The anti-Ramsey number AR n G for G is the maximum number of colors in an edge coloring of Kn that has no rainbow copy of any graph in G. The Turan number ex n G is the maximum number of edges of a simple graph without a copy of any graph in G . Clearly by taking one edge of each color in an edge coloring of Kn one can show that AR n G ex n G . When G consists of a single graph H we write AR m H and ex n H for AR m H and ex n H respectively. Anti-Ramsey numbers were introduced by Erdos et al. in 5 and showed to be connected not so much to Ramsey theory than to Turan numbers. In particular it was proved that AR n H ex n H o n2 where H H e e G E H . By THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R85 1 the asymptotic of Turan numbers we have AR n H n 1 - 1 d as n X where d 1 min x H e e G E H . So the anti-Ramsey number AR n H is determined asymptotically for graphs H with min x H e e G E H 3. The case min x H e e G E H 2 remains harder. The anti-Ramsey numbers for some special graph classes have been determined. As conjectured by Erdos
