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.
