# Strong colouring of matroid-graph pairs

From Egres Open

Let *G=(V,E)* be a graph with maximum degree [math]\Delta \geq 2[/math], and let *M=(V,r)* be a matroid that has [math]2 \Delta[/math] disjoint bases. Is it true that *M* has [math]2 \Delta[/math] disjoint bases that are all independent in *G*?

## Remarks

Aharoni and Berger ^{[1]} proved that if the condition holds, then *M* has a *G*-independent base. This was improved by Aharoni, Berger, and Sprüssel ^{[2]}: if [math]\Delta \geq 3[/math] and the condition holds, then *M* has two disjoint *G*-independent bases (interestingly, the case [math]\Delta =2[/math] is open).

## References

- ↑ R. Aharoni, E. Berger,
*The intersection of a matroid with a simplicial complex*, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. DOI link, JSTOR link - ↑ R. Aharoni, E. Berger, P. Sprüssel,
*Two Disjoint Independent Bases in Matroid-Graph Pairs*, DOI link