Department of
Applied
Mathematics

Rainbow Matchings in Graphs

Florian Pfender

Universität Rostock

Abstract

A rainbow subgraph in an edge colored graph is a subgraph whose edges are all colored differently. In this talk we will look at rainbow matchings, i.e. sets of pairwise disjoint edges whith distinct colors. This topic has connections to both Latin squares and to matchings in 3-uniform hypergraphs. We will study conditions which guarantee the existence of large rainbow matchings, i.e. sets of pairwise disjoint edges. Further, we will be surprised by the complexity of finding rainbow matchings in very simple graphs.