Large rainbow matchings in edge-coloured graphs

Alexandr Kostochka, Matthew Yancey

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)255-263
Number of pages9
JournalCombinatorics Probability and Computing
Volume21
Issue number1-2
DOIs
StatePublished - Jan 1 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Large rainbow matchings in edge-coloured graphs'. Together they form a unique fingerprint.

Cite this