Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-06T02:44:44.054Z Has data issue: false hasContentIssue false
  • English
  • Français

Large Rainbow Matchings in Edge-Coloured Graphs

Published online by Cambridge University Press:  02 February 2012

ALEXANDR KOSTOCHKA  and
MATTHEW YANCEY
ALEXANDR KOSTOCHKA
Affiliation:
Sobolev Institute of Mathematics, Novosibirsk 630090, Russia (e-mail: kostochk@math.uiuc.edu) Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: yancey1@illinois.edu)
MATTHEW YANCEY
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: yancey1@illinois.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A rainbow subgraph of an edge-coloured graph is a subgraph whose edges have distinct colours. The colour degree of a vertex v is the number of different colours on edges incident with v. Wang and Li conjectured that for k ≥ 4, every edge-coloured graph with minimum colour degree k contains a rainbow matching of size at least ⌈k/2⌉. A properly edge-coloured K4 has no such matching, which motivates the restriction k ≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 255 - 263
Copyright
Copyright © Cambridge University Press 2012

References

[1]Kano, M. and Li, X. (2008) Monochromatic and heterochromatic subgraphs in edge-colored graphs: A survey. Graphs Combin. 24 237–263.Google Scholar
[2]LeSaulnier, T. D., Stocker, C., Wegner, P. S. and West, D. B. (2010) Rainbow matching in edge-colored graphs. Electron. J. Combin. 17 N26.CrossRefGoogle Scholar
[3]Li, H. and Wang, G. (2008) Color degree and heterochromatic matchings in edge-colored bipartite graphs. Util. Math. 77 145–154.Google Scholar
[4]Li, X. and Xu, Z. (2007) On the existence of a rainbow 1-factor in proper coloring of Krn (r). arXiv:0711.2847 [math.CO].Google Scholar
[5]Wang, G. and Li, H. (2008) Heterochromatic matchings in edge-colored graphs. Electron. J. Combin. 15 R138.CrossRefGoogle Scholar