Strong colouring of matroid-graph pairs

From Egres Open
Jump to: navigation, search

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?


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).


  1. 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
  2. R. Aharoni, E. Berger, P. Sprüssel, Two Disjoint Independent Bases in Matroid-Graph Pairs, DOI link