# List colouring of two matroids

Given some matroids on the same ground set $S$, a colouring of $S$ is called proper if each monochromatic set is independent in each matroid. Let $M_1$ and $M_2$ be two matroids on ground set $S$, and suppose that there is a proper colouring by $k$ colours. Is it true that $M_1$ and $M_2$ can be k-list-coloured, i.e. for arbitrary lists $L_s$ of k colours for each $s \in S$, 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

1. P. D. Seymour, A note on list arboricity, J. Combin. Theory Ser. B 72 (1998), 150-151. DOI link.
2. M. Lasoń, W. Lubawski, On-line list coloring of matroids, arXiv link
3. F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63(1) (1995), 153-158. DOI link.
4. 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
5. T. Király, J. Pap, On the list colouring of two matroids, EGRES Quick Proof no. 2010-01