A Note on Large Rainbow Matchings in Edge-coloured Graphs

被引：12

作者：

Lo, Allan ^{[1
]}

Tan, Ta Sheng ^{[2
]}

机构：

[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England

[2] Univ Cambridge, Dept Pure Math & Math Stat, Ctr Math Sci, Cambridge CB3 0WB, England

来源：

GRAPHS AND COMBINATORICS | 2014年 / 30卷 / 02期

基金：

欧洲研究理事会;

关键词：

Matching; Edge colouring; Rainbow; Properly coloured; Totally multicoloured;

D O I：

10.1007/s00373-012-1271-y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on n vertices with minimum colour degree at least k contains a rainbow matching of size at least k, provided . In this paper, we show that n a parts per thousand yen 4k - 4 is sufficient for k a parts per thousand yen 4.

引用

页码：389 / 393

页数：5

共 15 条

[1]

[Anonymous], 1991, ENCY MATH ITS APPL

[2]

Diemunsch J., 2012, Electron. J. Combin, V19, P52

[3]

Diemunsch J., 2011, ARXIV11082521

[4]

Gyarfas A., 2012, ARXIV12085670V1

[5] Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey [J].

Kano, Mikio ;

Li, Xueliang .

GRAPHS AND COMBINATORICS, 2008, 24 (04) :237-263

[6]

Kostochka A., 2012, ARXIV12043193

[7]

Kostochka A.V., COMMUNICATION

[8] Large Rainbow Matchings in Edge-Coloured Graphs [J].

Kostochka, Alexandr ;

Yancey, Matthew .

COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) :255-263

[9]

LeSaulnier TD, 2010, ELECTRON J COMB, V17

[10]

Lo A., 2011, ARXIV11085273

← 1 2 →