TAILIEUCHUNG - Báo cáo toán học: " On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph"

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 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học