# Edge-covering number of 2-polymatroids

Let *f* be a 2-polymatroid function on *S* that has a matroid representation [math]M=(S \times \{1,2\},r)[/math] with the following property: [math]|C\cap \{(e,1),(e,2)\}| \leq 1[/math] for every [math]e \in S[/math] and every circuit *C* of *M*. Is it true that [math]\beta(f) \leq \beta^*(f)+1[/math], i.e. the minimum cover by matchings is at most one more than the minimum fractional cover by matchings?

## Remarks

The conjecture was proposed by Aharoni, Berger, and Ziv ^{[1]}; they show that the statement does not hold for general 2-polymatroids. Using the techniques in ^{[2]}, one can prove that [math]\beta(f) \leq 2\beta^*(f)[/math] for any 2-polymatroid function *f* (see Theorem 3.6 in ^{[1]}).

The conjecture is a common generalization of the conjecture on Upper bound on common independent set cover and a version of the Goldberg-Seymour conjecture (Open Problem Garden) that states that the edge-colouring number of a multigraph is at most its fractional edge-colouring number plus one.

## References

- ↑
^{1.0}^{1.1}R. Aharoni, E. Berger, R. Ziv,*The edge covering number of the intersection of two matroids*, DOI link - ↑ R. Aharoni, E. Berger,
*The intersection of a matroid and a simplicial complex*, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. Journal link. Citeseer link.