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: Partitioning 3-colored complete graphs into three monochromatic cycles. | Partitioning 3-colored complete graphs into three monochromatic cycles Andras Gyarfas Miklos Ruszinko Computer and Automation Research Institute Hungarian Academy of Sciences Budapest . Box 63 Hungary H-1518 gyarfas ruszinko@ Gabor N. Sarkozy Computer Science Department Worcester Polytechnic Institute Worcester MA USA 01609 gsarkozy@ and Endre Szemeredi Computer Science Department Rutgers University New Brunswick NJ UsA 08903 szemered@ Computer and Automation Research Institute Hungarian Academy of Sciences Budapest . Box 63 Hungary H-1518 Submitted Aug 10 2010 Accepted Mar 3 2011 Published Mar 11 2011 Mathematics Subject Classification 05C38 05C55 Abstract We show in this paper that in every 3-coloring of the edges of Kn all but o n of its vertices can be partitioned into three monochromatic cycles. From this using our earlier results actually it follows that we can partition all the vertices into at most 17 monochromatic cycles improving the best known bounds. If the colors of the three monochromatic cycles must be different then one can cover 3 o 1 n vertices and this is close to best possible. 1 Introduction It was conjectured in 8 that in every r-coloring of a complete graph the vertex set can be covered by r vertex disjoint monochromatic cycles where vertices edges and the empty set are accepted as cycles . The first three authors were supported in part by OTKA Grant K68322. The third author was also supported in part by a Janos Bolyai Research Scholarship and by NSF Grant DMS-0968699 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P53 1 Conjecture 1 Erdos Gyarfas Pyber 8 . In every r-coloring of the edges of Kn its vertex set can be partitioned into r monochromatic cycles. For general r the O r2 logr bound of Erdos Gyarfas and Pyber 8 has been improved to O rlogr by Gyarfas Ruszinko Sarkozy and Szemeredi 11 . The case r 2 was conjectured earlier by Lehel and was settled by Luczak Rodl and Szemeredi 16 for large n using
