Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (3): 77-90.doi: 10.15960/j.cnki.issn.1007-6093.2019.03.006

Previous Articles     Next Articles

A survey on rainbow matchings in graphs and hypergraphs

LI Tong, WANG Guanghui, ZHOU Wenling*   

  1. School of Mathematics, Shandong University, Jinan 250100, China
  • Received:2019-06-25 Published:2019-09-09

Abstract: A hypergraph H=(V, E) is a two-tuple (V, E), where the element in the hyperedge set E is a non-empty subset of the vertex set V. Therefore, the graph is a special hypergraph, and the hypergraph can also be regarded as a generalization of the general graph. In particular, if the elements in the hyperedge set E are all a k-subset of the vertex set V, then the hypergraph is said to be k-uniform. Usually, for the sake of simplicity, we will also refer to the hyperedge as the edge. A matching in a graph (hypergraph) refers to a collection of mutually disjoint edges in a graph (hypergraph). There are two ways to define a rainbow matching:one is a collection of mutually disjoint edges with different colors in an edge-colored graph(hypergraph); the other one is a collection of mutually disjoint edges with different colors, where each edge is from different edge-colored graphs(hypergraphs). This paper mainly introduces the results related to rainbow matchings in graphs and hypergraphs.

Key words: graph, hypergraph, matching, rainbow matching

CLC Number: