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 matchings in properly edge colored graphs. | Rainbow matchings in properly edge colored graphs Guanghui Wang School of Mathematics Shandong University Jinan Shandong 250100 . China ghwang@ Submitted Mar 14 2011 Accepted Jul 20 2011 Published Aug 5 2011 Mathematics Subject Classifications 05C15 05C70 Abstract Let G be a properly edge colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let Ỗ denote the minimum degree of G. We show that if V G 8f then G has a rainbow matching of size at least L35 J. We also prove that if G is a properly colored triangle-free graph then G has a rainbow matching of size at least LyJ. Keywords rainbow matchings properly colored graphs triangle-free graphs 1 Introduction and notation We use 3 for terminology and notations not defined here and consider simple undirected graphs only. Let G V E be a graph. A proper edge-coloring of G is a function c E N N is the set of nonnegative integers such that any two adjacent edges have distinct colors. If G is assigned such a coloring c then we say that G is a properly edgecolored graph or simply a properly colored graph. Let c e denote the color of the edge e G E. For a subgraph H of G let c H c e e G E H . A subgraph H of G is called rainbow if its edges have distinct colors. Recently rainbow subgraphs have received much attention see the survey paper 8 . Here we are interested in rainbow matchings. The study of rainbow matchings began with the following conjectures. Conjecture 1 Ryser 5 Every Latin square of odd order has a Latin transversal. Conjecture 2 Brualdi-Stein 9 11 Every latin square of order n has a partial Latin transversal of size at least n 1. An equivalent statement is that every proper n-edge-coloring of the complete bipartite graph Kn n contains a rainbow matching of size n 1 Moreover if n is odd there exists THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P162 1 a rainbow perfect matching. Hatami and Shor 7 proved that there is always a partial Latin transversal .