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?
It is known by an observation of Seymour that the list colouring theorem holds for one matroid. Lasoń and Lubawski  proved an online version, where colours are revealed one by one on the lists. Galvin  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  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  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!
- 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