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 colorings avoiding a rainbow cycle and a fixed monochromatic subgraph. | On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph Maria Axenovich JiHyeok Choi Department of Mathematics Iowa State University Ames IA 50011 axenovic@ jchoi@ Submitted Apr 23 2009 Accepted Feb 7 2010 Published Feb 22 2010 Mathematics Subject Classification 05C15 05C55 Abstract Let H and G be two graphs on fixed number of vertices. An edge coloring of a complete graph is called H G -good if there is no monochromatic copy of G and no rainbow totally multicolored copy of H in this coloring. As shown by Jamison and West an H G -good coloring of an arbitrarily large complete graph exists unless either G is a star or H is a forest. The largest number of colors in an H G -good coloring of Kn is denoted maxR n G H . For graphs H which can not be vertex-partitioned into at most two induced forests maxR n G H has been determined asymptotically. Determining maxR n G H is challenging for other graphs H in particular for bipartite graphs or even for cycles. This manuscript treats the case when H is a cycle. The value of maxR n G Ck is determined for all graphs G whose edges do not induce a star. 1 Introduction and main results For two graphs G and H an edge coloring of a complete graph is called H G -good if there is no monochromatic copy of G and no rainbow totally multicolored copy of H in this coloring. The mixed anti-Ramsey numbers maxR n G H minR n G H are the maximum minimum number of colors in an H G -good coloring of Kn respectively. The number maxR n G H is closely related to the classical anti-Ramsey number AR n H the largest number of colors in an edge-coloring of Kn with no rainbow copy of H introduced by Erdos Simonovits and Sos 9 . The number minR n G H is closely related to The first author s research supported in part by NSA grant H98230-09-1-0063 and NSF grant DMS-0901008. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R31 1 the classical multicolor Ramsey number Rk G the largest n such that there is a coloring of .
