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
    Kano, Mikio
    Li, Xueliang
    [J]. 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
    Kostochka, Alexandr
    Yancey, Matthew
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) : 255 - 263
  • [9] LeSaulnier TD, 2010, ELECTRON J COMB, V17
  • [10] Lo A., 2011, ARXIV11085273
12