作者：Ferhat, Dehia Ait; Kiraly, Zoltan; Sebo, Andras; Stauffer, Gautier
作者单位：Mentor Graphics Inc; Eotvos Lorand University; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University of Lausanne
摘要：Given an undirected graph, are there k matchings whose union covers all of its nodes, that is, a matching-k-cover? When k = 1, the problem is equivalent to the existence of a perfect matching for which Tutte's celebrated matching theorem (J. Lon. Math. Soc., 1947) provides a `good' characterization. We prove here, when k is greater than one, a `good' characterization a la Konig: for k >= 2, there exist k matchings covering every node if and only if for every stable set S, we have vertical bar ...
作者：Herings, P. Jean-Jacques; Zhan, Yang
作者单位：Tilburg University; Nanjing University; Nanjing University
