Multimatroids I. Coverings by Independent Sets

Abstract

Multimatroids are combinatorial structures that generalize matroids and arise in the study of Eulerian graphs. We prove, by means of an efficient algorithm, a covering theorem for multimatroids. This theorem extends Edmonds' covering theorem for matroids. It also generalizes a theorem of Jackson on the Euler tours of a 4-regular graph.