Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Rainbow k-Matching in the Complete Graph with r Colors. | A Rainbow k-Matching in the Complete Graph with r Colors Shinya Fujita1 Atsushi Kaneko Ingo Schiermeyer2 and Kazuhiro Suzuki3 1 Department of Mathematics Gunma National College of Technology 580 Toriba Maebashi Gunma 371-8530 Japan shinyaa@ 2 Institut fur Diskrete Mathematik und Algebra Technische Universitat Bergakademie Freiberg 09596 Freiberg Germany schierme@ 3 Department of Computer and Information Sciences Ibaraki University Hitachi Ibaraki 316-8511 Japan tutetuti@ Submitted Dec 31 2007 Accepted Apr 18 2009 Published Apr 30 2009 Mathematics Subject Classifications 05C15f 05C70 Abstract An r-edge-coloring of a graph is an assignment of r colors to the edges of the graph. An exactly r-edge-coloring of a graph is an r-edge-coloring of the graph that uses all r colors. A matching of an edge-colored graph is called rainbow matching if no two edges have the same color in the matching. In this paper we prove that an exactly r-edge-colored complete graph of order n has a rainbow matching of size 9 mm-Ị i2k 3 I 9 fk-2f I o I 9 I 91 0 9 and II 9 k I 1 k 2 n r 11 Lax 2 y I 2 2 k 2 n k I 2 I 2 k 2 and In _ 2 k I 1. The bound on r is best possible. Keyword s edge-coloring matching complete graph anti-Ramsey rainbow heterochromatic totally multicolored 1 Introduction We consider finite undirected simple graphs G with the vertex set V G and the edge set E G . An r-edge-coloring of a graph G is a mapping color E G C where C is Corresponding author Present affiliation is Department of Electronics and Informatics Frontier Kanagawa University Yokohama Kanagawa 221-8686 Japan. 050 5 Coloring of graphs and hypergraphs 05C70 Factorization matching covering and packing THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R51 1 a set of r colors. An exactly r-edge-coloring of a graph is an r-edge-coloring of the graph such that all r colors is used namely every color appears in the r-edge-colored graph. A subgraph H of an edge-colored graph is
