Strong colouring of matroid-graph pairs
From Egres Open
(Redirected from Strong colouring of matroids)
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
