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:Rainbow Matching in Edge-Colored Graphs. | Rainbow Matching in Edge-Colored Graphs Timothy D. LeSaulnier Paul S. Wenger Christopher Stocker Douglas B. West Submitted Dec 29 2009 Accepted May 7 2010 Published May 14 2010 Mathematics Subject Classification 05C15 05C35 05C55 05C70 Abstract A rainbow subgraph of an edge-colored graph is a subgraph whose edges have distinct colors. The color degree of a vertex v is the number of different colors on edges incident to v. Wang and Li conjectured that for k 4 every edge-colored graph with minimum color degree at least k contains a rainbow matching of size at least k 2 . We prove the slightly weaker statement that a rainbow matching of size at least k 2 is guaranteed. We also give sufficient conditions for a rainbow matching of size at least k 2 that fail to hold only for finitely many exceptions for each odd k . 1 Introduction Given a coloring of the edges of a graph a rainbow matching is a matching whose edges have distinct colors. The study of rainbow matchings began with Ryser who conjectured that every Latin square of odd order contains a Latin transversal 3 . An equivalent statement is that when n is odd every proper n-edge-coloring of the complete bipartite graph Kn n contains a rainbow perfect matching. Wang and Li 4 studied rainbow matchings in arbitrary edge-colored graphs. We use the model of graphs without loops or multi-edges. The color degree of a vertex v in an edge-colored graph G written dG v is the number of different colors on edges incident to v. The minimum color degree of G denoted 5 G is minvey G dG v . Wang and Li 4 proved that every edge-colored graph G contains a rainbow matching of size at least p50 G2 31. They conjectured that a rainbow matching of size at least Department of Mathematics University of Illinois Urbana IL 61801. Email addresses tlesaul2@ stocker2@ pwenger2@ west@. Contact author partially supported by NSF grant DMS 08-38434 EMSW21-MCTP Research Experience for Graduate Students. Research .
