tailieunhanh - Báo cáo toán học: "Rainbow matchings in properly edge colored graphs"

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 .