# List colouring of two matroids

Given some matroids on the same ground set [math]S[/math], a colouring of [math]S[/math] is called **proper** if each monochromatic set is independent in each matroid.
Let [math]M_1[/math] and [math]M_2[/math] be two matroids on ground set [math]S[/math], and suppose that there is a proper colouring by [math]k[/math] colours.
Is it true that [math]M_1[/math] and [math]M_2[/math] can be *k*-list-coloured, i.e. for arbitrary lists [math]L_s[/math] of *k* colours for each [math]s \in S[/math], there is a proper colouring that uses colours from these lists?

## Remarks

It is known by an observation of Seymour^{[1]} that the list colouring theorem holds for one matroid. Lasoń and Lubawski ^{[2]} proved an online version, where colours are revealed one by one on the lists. Galvin ^{[3]} proved the list-edge-coloring theorem for bipartite graphs, an intersection of two partition matroids. A possible direction is to consider further classes of matroids where there is a partition theorem for common bases, like branchings or strongly base orderable matroids.

Tamás Fleiner ^{[4]} formulated a generalization of the bipartite stable matching theorem for matroid kernels. This may be a useful tool in the study of generalizations of edge-list-colorings, considering that the bipartite list-edge-colouring theorem was proved using stable matchings by Galvin.

In ^{[5]} the property is shown for some special cases: if the matroids are transversal, if they are of rank two, and if the common bases are the arborescences of a digraph and *k*=2.

See the discussion page for comments and new developments!

## References

- ↑ P. D. Seymour,
*A note on list arboricity*, J. Combin. Theory Ser. B 72 (1998), 150-151. DOI link. - ↑ M. Lasoń, W. Lubawski,
*On-line list coloring of matroids*, arXiv link - ↑ F. Galvin,
*The list chromatic index of a bipartite multigraph*, J. Combin. Theory Ser. B 63(1) (1995), 153-158. DOI link. - ↑ T. Fleiner,
*A fixed-point approach to stable matchings and some applications*, Mathematics of Operations Research 28 (2003), 103-126. Journal link. EGRES Technical Report no. 2001-01 - ↑ T. Király, J. Pap,
*On the list colouring of two matroids*, EGRES Quick Proof no. 2010-01