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
