Rainbow Matchings of size $m$ in Graphs with Total Color Degree at least $2mn$

  • Jürgen Kritschgau

Abstract

The existence of a rainbow matching given a minimum color degree, proper coloring, or triangle-free host graph has been studied extensively. This paper generalizes these problems to edge colored graphs with given total color degree. In particular, we find that if a graph $G$ has total color degree $2mn$ and satisfies some other properties, then $G$ contains a matching of size $m$. These other properties include $G$ being triangle-free, $C_4$-free, properly colored, or large enough. 

Published
2020-07-24
Article Number
P3.18