Existence of rainbow matchings in strongly edge-colored graphs

doi:10.1016/j.disc.2016.04.016

CSpace > 应用数学研究所

	Existence of rainbow matchings in strongly edge-colored graphs
	Wang, Guanghui 1; Yan, Guiying2 ; Yu, Xiaowei 1
	2016-10-06
发表期刊	DISCRETE MATHEMATICS
ISSN	0012-365X
卷号	339 期号:10 页码:2457-2460
摘要	The famous Ryser Conjecture states that there is a transversal of size n in a latin square of odd order n, which is equivalent to finding a rainbow matching of size n in a properly edge-colored K-n,K-n when n is odd. Let delta denote the minimum degree of a graph. In 2011, Wang proposed a more general question to find a function f (delta) (f (delta) >= 2 delta + 1) such that for each properly edge-colored graph of order f (delta), there exists a rainbow matching of size delta. The best bound so far is f (delta) <= 3.5 delta + 2 due to Lo. Babu et al. considered this problem in strongly edge-colored graphs in which each path of length 3 is rainbow. They proved that if G is a strongly edge-colored graph of order at least 2 left perpendicular3 delta/4right perpendicular, then G has a rainbow matching of size left perpendicular3 delta/4right perpendicular. They proposed an interesting question: Is there a constant c greater than such that every strongly edge-colored graph G has a rainbow matching of size at least c delta if vertical bar V(G)vertical bar >= 2 left perpendicularc delta right perpendicular ? Clearly, c <= 1. We prove that if G is a strongly edge-colored graph with minimum degree 8 and order at least 2 delta + 2, then G has a rainbow matching of size delta. (C) 2016 Elsevier B.V. All rights reserved.
关键词	Rainbow matchings Strongly edge-colored graphs Latin square
DOI	10.1016/j.disc.2016.04.016
语种	英语
资助项目	National Natural Science Foundation of China[11371355] ; National Natural Science Foundation of China[11471193] ; Foundation for Distinguished Young Scholars of Shandong Province[JQ201501] ; Independent Innovation Foundation of Shandong University[IFYF14012] ; Fundamental Research Funds of Shandong University
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000379281200008
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/23145
专题	应用数学研究所
通讯作者	Wang, Guanghui
作者单位	1.Shandong Univ, Sch Math, Jinan 250100, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 10080, Peoples R China
推荐引用方式 GB/T 7714	Wang, Guanghui,Yan, Guiying,Yu, Xiaowei. Existence of rainbow matchings in strongly edge-colored graphs[J]. DISCRETE MATHEMATICS,2016,339(10):2457-2460.
APA	Wang, Guanghui,Yan, Guiying,&Yu, Xiaowei.(2016).Existence of rainbow matchings in strongly edge-colored graphs.DISCRETE MATHEMATICS,339(10),2457-2460.
MLA	Wang, Guanghui,et al."Existence of rainbow matchings in strongly edge-colored graphs".DISCRETE MATHEMATICS 339.10(2016):2457-2460.