Existence of rainbow matchings in properly edge-colored graphs

被引：7

作者：

Wang, Guanghui ^{[1
]}

Zhang, Jianghua ^{[2
]}

Liu, Guizhen ^{[1
]}

机构：

[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China

[2] Shandong Univ, Sch Management, Jinan 250100, Peoples R China

来源：

FRONTIERS OF MATHEMATICS IN CHINA | 2012年 / 7卷 / 03期

基金：

中国国家自然科学基金; 高等学校博士学科点专项科研基金;

关键词：

Rainbow matching; properly edge-colored graph;

D O I：

10.1007/s11464-012-0202-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let be a properly edge-colored graph. A rainbow matching of is a matching in which no two edges have the same color. Let denote the minimum degree of . We show that if |()| > ( (2) + 14 + 1)/4, then has a rainbow matching of size , which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that if is a properly colored bipartite graph with bipartition () and max{||, ||} > ( (2) + 4 - 4)/4, then has a rainbow matching of size .

引用

页码：543 / 550

页数：8

共 11 条

[1] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[2] Brualdi R.A., 1991, Encyclopedia of Mathematics and Its Applications, V39
[3] Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
Kano, Mikio
Li, Xueliang
[J]. GRAPHS AND COMBINATORICS, 2008, 24 (04) : 237 - 263
[4] Kostochka A, COMBIN PROB IN PRESS
[5] LeSaulnier TD, 2010, ELECTRON J COMB, V17
[6] Li H, 2008, UTILITAS MATHEMATICA, V77, P145
[7] Ryser H. J., 1967, MATH FORSCHUNGSINSTI, P24
[8] Stein KS., 1975, PAC J MATH, V59, P567
[9] Wang GH, 2008, ELECTRON J COMB, V15
[10] Wang GH, 2011, ELECTRON J COMB, V18

← 1 2 →