Talk:List colouring of two matroids
Contents
Some suggested matroid classes -- Tamás Király 14:19, 13 July 2012 (UTC)
Some fairly simple classes where we do not know the answer:
- truncations of transversal matroids
- spanning arborescences, for [math]k \geq 3[/math]
- matroids of rank 3
- a partition matroid and an arbitrary matroid
The last one may also be a good place to look for counterexamples.
What about more matroids? -- Dom 19:47, 13 July 2012 (UTC)
Is there a counterexample or is it also open?
Re: What about more matroids? -- Tamás Király 21:33, 13 July 2012 (UTC)
If we allow 3 matroids, then we can have a ground set of size 6 where the circuits of the 3 matroids form a [math]K_{3,3} [/math], so there is a partition into two common bases. If the colour lists are {1,2}, {1,3}, {2,3} in both bases, then there is no proper list colouring.
Another interesting special case -- Tamás Király 13:24, 3 September 2012 (UTC)
The following special case of the problem has a flavor similar to Rota's conjecture (Open Problem Garden). Let M be a matroid of rank k+1 whose ground set can be partitioned into k bases [math]B_1,\dots,B_k[/math]. Let furthermore [math]S_1,\dots,S_{k+1}[/math] be a partition such that [math]|B_i \cap S_j|=1[/math] for every i,j. Is it true that the ground set can be partitioned into independent sets [math]F_1,\dots,F_{k+1}[/math] such that [math]F_i \cap S_i=\emptyset[/math] and [math]|F_i \cap S_j|=1[/math] if [math]i \neq j[/math]?
Re: Another interesting special case -- Tamás Király (talk) 12:41, 29 July 2013 (UTC)
- Note that this would follow from the matroid generalization of of the conjecture on Rainbow matchings in bipartite graphs. Indeed, let [math]M_2[/math] be the partition matroid defined by [math]S_1,\dots,S_{k+1}[/math]. If there is a transversal that is a common independent set, then we can take that as one set, and the remaining parts of [math]B_1,\dots,B_k[/math] as the other k sets.
Longer lists -- Tamás Király (talk) 16:50, 26 September 2013 (UTC)
One may try to find a constant c such that if there is a proper colouring by k colours and every list has size ck, then there is a proper list colouring. For spanning arborescences, it was observed by Yusuke Kobayashi that the constructive characterization of k-arborescences implies that lists of size [math]\frac{3}{2}k+1[/math] are sufficient.
